刷题篇--翻转二叉树

翻转二叉树

leetcode 226题，翻转二叉树。本文使用递归和非递归两种方法解体。从这些题目中可以看出，树的问题，往往可以递归和非递归两种方式完成，并且和其深度遍历、广度遍历相关。

1.递归

def invertTree(root): if root is None: return root #递归必有终止条件 root.left, root.right = root.right, root.left self.invertTree(root.left) #左右子树分别翻转，递归下去 self.invertTree(root.right) return root

从递归来看，其就是不断递归左右子树。

2.非递归

非递归方法可以从树的广度优先遍历入手，每一层的节点分别交换左右节点。

def invertTree(root): if root is None: return root queue = [root] while queue: temp = [] for node in queue: node.left, node.right = node.right, node.left if node.left: temp.append(node.left) if node.right: temp.append(node.right) queue = temp return root