前序遍历
先根节点，再左边子树，然后右边子树
递归遍历:
# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
def helper(node):
if node == None:
return
result.append(node.val)
helper(node.left)
helper(node.right)
result = []
helper(root)
return result
迭代遍历：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
if not root:
return ans
stack = [root]
while stack:
node = stack.pop() # 这个弹出很重要，将已经遍历的跟节点剔除，这样就不需要再进行是否已经遍历的判断
ans.append(node.val)
if node.right: # 这里先加入根节点的右边节点，再加入左边节点。这样取的时候先取左边子节点
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans
中序遍历
先是左节点，再是中间根节点，最后右边子节点。
递归解法：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
res = []
def helper(node):
if node== None: # 停止递归的条件
return
helper(node.left)
res.append(node.val)
helper(node.right)
helper(root)
return res
更简洁的递归解法：
def inorder(r):
return inorder(r.left) + [r.val] + inorder(r.right) if r else []
迭代解法：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root == None:
return []
res = []
stack = []
while stack or root != None:
while root: # 这个while循环一直遍历到二叉树最左边的叶节点
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
后序遍历
递归解法，根节点最后遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def postorder(root: TreeNode):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
res = list()
postorder(root)
return res
迭代解法：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return list()
res = list()
stack = list()
prev = None
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if not root.right or root.right == prev:
res.append(root.val)
prev = root
root = None
else:
stack.append(root)
root = root.right
return res
运用递归解决树的问题
自顶向下
主题思想：
- 能确定一些参数，从该节点自身解决出发寻找答案吗？
- 可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
例如对于求一个二叉树的最大深度的问题，其伪代码为：
return if root is null
if root is a leaf node:
answer = max(answer, depth) // update the answer if needed
maximum_depth(root.left, depth + 1) // call the function recursively for left child
maximum_depth(root.right, depth + 1) // call the function recursively for right child
python实现为：
class Solution:
def maxDepth(self, root: TreeNode) -> int:
answer = 0
def helper(root , depth):
nonlocal answer # 这里一定要用nonlocal，不能用global
if root == None :
return
if root.left == None and root.right == None :
answer = max(answer , depth)
helper(root.left , depth + 1)
helper(root.right , depth + 1)
helper(root , 1)
return answer
自底向上
在每个递归层次上，首先对所有子节点递归的调用函数，然后根据返回值和根节点本身的值得到答案。可以看做是后序遍历的一种。递归函数bottom_up(root)：
1. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
C++实现
int maximum_depth(TreeNode* root) {
if (!root) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root->left);
int right_depth = maximum_depth(root->right);
return max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}
对称二叉树
判断一棵树是否是对称的（镜像的）
python实现递归：
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.isSymmetricTree(root.left, root.right)
def isSymmetricTree(self, left, right):
if left is None and right is None: return True #同时为空
if left is None or right is None : return False #一个为空
if left.val != right.val : return False # 值不相等 ！！
return self.isSymmetricTree(left.left, right.right) and self.isSymmetricTree(left.right, right.left)
python实现迭代：
比较一棵二叉树是否是对称的等同于比较以同样根节点一模一样的树是否是镜像的。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def check(u , v):
q = Deque()
q.append(u)
q.append(v)
while q:
u = q.pop()
v = q.pop()
if u == None and v == None:
continue
if (u == None or v == None):
return False
if u.val != v.val :
return False
q.append(u.left)
q.append(v.right)
q.append(u.right)
q.append(v.left)
return True
return check(root,root)
路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
python递归解法：
class Solution:
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
if root == None and targetSum == 0 :
return False
if root == None :
return False
if root.left == None and root.right == None:
if root.val == targetSum :
return True
return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
以上是运用自顶向下的思想。
最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
分治法解决该题：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 分治法的典型题
if root == None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if left!= None and right!= None : # 左边有值，右边也有值，说明左子树和右子树都存在某一个节点
return root
if left != None : # 右子树返回空，说明p,q都在左子树，所以结果就从left中选
return left
if right != None: # 左子树返回空，说明p,q都在右子树，所以结果就从right中选
return right
return None
总结一下二叉树遍历的诀窍：
- 先搞清楚当前root节点该做什么，然后根据函数定义递归调用子节点。递归调用会让子节点做相同的事情。
- 写递归算法关键要明确函数的定义，然后利用这个定义推到最终结果。一定一定不要陷入递归的细节。从已经完成的任务开始推。
- 二叉树的一个难点：怎么把题目细化成每一个节点需要做的事情。
例如：在树中有多少个节点的问题时：
def count(root):
if not root: return 0
return 1 + count(root.left) + count(root.right)
226.反转二叉树
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root : return None
tmp = root.left
root.left = root.right
root.right = tmp
self.invertTree(root.left)
self.invertTree(root.right)
return root
116. 填充二叉树节点的右侧指针
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root: return None
self.helper(root.left,root.right)
return root
def helper(self,node1,node2): # 将node1和node2两个相邻节点进行连接
if node1 == None or node2 == None :
return
# 将传入的两个节点连接
node1.next = node2
# 连接相同父节点的两个子节点
self.helper(node1.left,node1.right)
self.helper(node2.left,node2.right)
# 连接跨越父节点的两个子节点
self.helper(node1.right,node2.left)
剑指offer28. 对称二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
这一题和上面一题有相似的地方，如果一开始递归函数的定义并不是我们想要的，比如这一题：
isSymmetrics函数的定义是判断一棵以root为节点的二叉树，它是不是对称的。不能陷入误区:我们直接递归将root.left和root.right行不行？答案是不行，因为这样我们就只是在判断以root.left和root.right为根节点的两棵树它是不是对称的，显然不符合我们想要实现的目标。所以这时候我们就要加一个helper的递归函数来帮助我们判断：helper的主要功能是判断以L和R为根节点的树，他俩是不是对称的。
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root :
return True
def helper(L,R): # 判断以 L 和 R 为节点的二叉树是不是镜像对称
if not L and not R :
return True
if not L or not R :
return False
if L.val != R.val :
return False
if L.val == R.val :
return helper(L.left,R.right) and helper(L.right,R.left)
return helper(root.left,root.right)
总结：在完成二叉树的题目的时候，很多中等难度的题目要稍微改变一下递归的定义，如果这一个方法行不通，我们就可以换个思路。
