226.翻转二叉树
题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
思路
- 递归法
分析题目输入和输出发现，输出的左右子树的位置跟输入正好是相反的，于是我们可以递归的交换左右子树来实现。
其实就是交换一下左右节点，然后再递归的交换左节点，右节点
递归的两个条件如下：
终止条件：当前节点为 null 时返回
交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点时间复杂度：每个元素都必须访问一次，所以是 O(n)
空间复杂度：最坏的情况下，需要存放 O(h) 个函数调用(h是树的高度)，所以是 O(h) - 迭代法
递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。
广度优先遍历需要额外的数据结构–队列，来存放临时遍历到的元素。
我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。
对当前元素调换其左右子树的位置，然后：
判断其左子树是否为空，不为空就放入队列中
判断其右子树是否为空，不为空就放入队列中
时间复杂度：同样每个节点都需要入队列/出队列一次，所以是 O(n)
空间复杂度：最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是 n/2个，所以时间复杂度是 0(n)
代码
class TreeNode(object): # Definition for a binary tree node.
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def invertTree(self, root):
"""
递归法（深度优先遍历方式）
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return root
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
return root
def invertTree1(self, root):
"""迭代法（广度优先遍历方式，需要辅助队列）"""
if not root:
return root
# 将二叉树的节点逐层放入队列中，再迭代处理队列中的元素
queue = [root]
while queue:
# 每次都从队列中拿一个节点，并交换这个节点的左右子树
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
def preorder_traverse(self, root):
if not root:
return
print(root.val)
self.preorder_traverse(root.left)
self.preorder_traverse(root.right)
if __name__ == "__main__":
root = TreeNode(4)
node2 = TreeNode(2)
node3 = TreeNode(7)
node4 = TreeNode(1)
node5 = TreeNode(3)
node6 = TreeNode(6)
node7 = TreeNode(9)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7
slt = Solution()
# invertTree = slt.invertTree(root)
invertTree = slt.invertTree1(root)
slt.preorder_traverse(invertTree)