LeetCode226.翻转二叉树

题目

分析

翻转每个节点左右子树即可。

代码

前序遍历，递归法

 1 class Solution {
 2 public:
 3     TreeNode* invertTree(TreeNode* root) {
 4         if(root == NULL) return root;
 5         TreeNode* node = root->left;
 6         root->left = root->right; root->right = node;
 7         invertTree(root->left);
 8         invertTree(root->right);
 9         return root;
10     }
11 };

前序遍历，迭代法

 1 class Solution {
 2 public:
 3     TreeNode* invertTree(TreeNode* root) {
 4         if(root== NULL) return root;
 5         stack<TreeNode*>s;
 6         s.push(root);
 7         while(!s.empty()){
 8             auto t = s.top();
 9             s.pop();
10             swap(t->left,t->right);
11             if(t->right!=NULL) s.push(t->right);
12             if(t->left!=NULL) s.push(t->left);
13         }
14         return root;
15     }
16 };