题目
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9
输出：
4 / \ 7 2 / \ / \ 9 6 3 1
解题
只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次
方法一：递归
python 写法
前序遍历
class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None root.left, root.right = root.right, root.left #中 self.invertTree(root.left) #左 self.invertTree(root.right) #右 return root
后续遍历
```python class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None self.invertTree(root.left) #左 self.invertTree(root.right) #右 root.left, root.right = root.right, root.left #中 return root
但是中序遍历是不行的，如下
root.left先进行了反转，然后把root.right = root.left ， 相当于把之前的root.left又重新反转了一次，最后会导致错误。
class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None self.invertTree(root.left) #左 root.left, root.right = root.right, root.left #中 self.invertTree(root.right) #右 return root
c++ 写法
前序遍历
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return nullptr; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };
java写法
class Solution { public TreeNode invertTree(TreeNode root) { if(root==null) return root; root.left=invertTree(root.left); root.right=invertTree(root.right); TreeNode tmp=root.left; root.left=root.right; root.right=tmp; return root; } }
方法二：深度优先遍历（前序）
由于堆栈的后进先出,left最后才进入，先出来，从而实现了前序遍历
python 写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return root stack = [root] while stack: tmp = stack.pop() tmp.left,tmp.right = tmp.right,tmp.left if tmp.right: stack.append(tmp.right) if tmp.left: stack.append(tmp.left) return root
c++ 写法
方法三：广度优先遍历(层序)
python 写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return queue = [root] while queue: l = len(queue) for _ in range(l): tmp = queue.pop(0) tmp.left,tmp.right = tmp.right,tmp.left if tmp.left: queue.append(tmp.left) if tmp.right: queue.append(tmp.right) return root
c++ 写法
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return root; queue<TreeNode*> queue; queue.push(root); while(!queue.empty()){ int l=queue.size(); for(int i=0;i<l;i++){ TreeNode* cur=queue.front(); queue.pop(); swap(cur->left,cur->right); if(cur->left){ queue.push(cur->left); } if(cur->right){ queue.push(cur->right); } } } return root; } };
