二叉树的后续遍历

一、自底向上

二叉树自底向上的递归就是后续遍历，后续遍历在二叉树中非常非常重要，他能够先遍历左右子树的值，然后在返回到父节点，是一个非常非常理想的自底向上的逻辑。

几乎所有二叉树的题目，如果使用 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，以此类推。