翻转二叉树

leetcode链接

1.解法

解法思路：

想把二叉树翻转，其实仔细一看，就是把每个二叉树的节点的左右孩子翻转，这样总体效果就是把整个二叉树翻转了。

所以只需要通过一种遍历手段把所有节点都遍历了，然后把每个节点的左右孩子翻转即可。

遍历手段选择：

1. 前序遍历
2. 后序遍历
3. 层序遍历

这三种方式都可以，但是不要选择中序遍历。我们来考虑下面这棵树：

如果使用中序遍历（1234679）

1. 首先需要先遍历1节点，然后翻转左右孩子，左右孩子都是空节点。
2. 然后遍历2节点，翻转左右孩子1和3，树变成了下面这个模样。
   
3. 然后遍历2的右孩子，注意此时2的右孩子变为了1，但是我们的本意应该是想把3节点的左右孩子翻转，所以使用中序遍历会把某个节点（这个例子中是1节点）的左右孩子翻转两次，还会使得某个节点（这个例子中是3节点）的左右孩子不翻转。所以最好不要使用这种方法。

下面把前序遍历（迭代法和递归法）和层序遍历的解题代码给出：

前序遍历（迭代法）：

def invertTree(root):stack = []if root:stack.append(root)while stack:node = stack.pop()# 把该节点的左右孩子反转node.left,node.right = node.right,node.left# 如果右孩子不为空if node.right:stack.append(node.right)# 如果左孩子不为空if node.left:stack.append(node.left)return root

前序遍历（递归法）：

def invertTree(root):if root == None:return rootroot.left,root.right = root.right,root.leftinvertTree(root.left)invertTree(root.right)return root

层序遍历：

def invertTree(root):queue = []if root:queue.append(root)while queue:size = len(queue)for i in range(size):node = queue.pop(0)node.left, node.right = node.right, node.leftif node.left != None:queue.append(node.left)if node.right != None:queue.append(node.right)return root

2.总结

算法

1. 有些题的表面看起来会很复杂，但是其实里面的解法思路并不困难，不要把问题想复杂。
2. 翻转二叉树步骤：
   （1）遍历每个节点
   （2）翻转每个节点的左右孩子
   （3）注意不要使用中序遍历