一、自底向上
二叉树自底向上的递归就是后续遍历，后续遍历在二叉树中非常非常重要，他能够先遍历左右子树的值，然后在返回到父节点，是一个非常非常理想的自底向上的逻辑。
几乎所有二叉树的题目，如果使用 dfs，都需要二叉树的后续遍历逻辑。因为都需要考虑最简单的节点的左右节点情况，然后再往上依次扩大规模。
一般我们做二叉树的题目，比如求二叉树的深度，都会这样写：
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
都是先求左边，然后求右边，然后依次向上。而这个代码实际上的运行顺序就是先到最后一个节点，然后看left和right，然后往上。然后看最后一个节点的（此时变成 left）的父节点的 right，以此类推。
网友评论