LCR 144. 翻轉二叉樹 - 力扣（LeetCode）

給定一棵二叉樹的根節點?root，請左右翻轉這棵二叉樹，并返回其根節點。

示例 1：

輸入：root = [5,7,9,8,3,2,4]
輸出：[5,9,7,4,2,3,8]

提示：

• 樹中節點數目范圍在?[0, 100]?內
• -100 <= Node.val <= 100

題解

前序遍歷圖解

?

?

代碼

遞歸算法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(!root) return nullptr;swap(root->left,root->right);mirrorTree(root->left);mirrorTree(root->right);return root;}
};

非遞歸算法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(!root) return nullptr;stack<TreeNode*> s;s.push(root);while(!s.empty()){TreeNode* node=s.top();s.pop();swap(node->left,node->right);if(node->left) s.push(node->left);if(node->right) s.push(node->right);}return root;}
};