后序遍历-自底向上的思想

在二叉树类型的问题中，常常求解最大和、最长路径等的问题，可以按照自底向上的思路进行处理，也就是说，从树的底部开始分析，将可能的最大结果一步一步地向上汇总，直到抵达树的根部。

下满例举两个这种类型的题目。

1. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

Ref: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

分析

题目中所定义的路径实际上可以拆分为路径的 左半、右半和连接节点。我们所需要做的，就是寻找这样的连接节点，使得它的左半 + 右半 + 自身 的和最大。

在遍历过程中，我们需要不断的计算节点最大左半和右半的大小。这一过程可以使用递推的方式：“节点的最大左半 = 节点的左子节点 + max(左子节点的最大左半，左子节点的最大右半)”。

因此，在遍历过程中，我们需要返回的值是当前节点的 “节点值 + max(节点的左半最大值，节点的右半最大值)”，上层节点根据这一返回值，进一步计算出上层节点对应的返回值，并同时，判断是否需要跟新最大路径值。

依照上述思路，从树的底层自底向上遍历。

参考下述代码：

class Solution {
    int maxVal = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return maxVal;
    }

    // 返回最大贡献值
    int maxSum(TreeNode node){
        // null 结点贡献值为 0
        if(node == null) return 0;

        // 计算左右结点的最大贡献值 -- 如果是负值，则贡献值为 0
        int maxLeft = Math.max(maxSum(node.left), 0);
        int maxRight = Math.max(maxSum(node.right), 0);

        // 更新 截至 当前节点的 最大路径和
        // 最大路径和 = 当前节点值 + 左子节点最大贡献值 + 右子节点最大贡献值
        // 如果大于当前记录到的最大值，则更新
        maxVal = Math.max(maxVal, node.val + maxLeft + maxRight);

        // 计算最大贡献值
        return node.val + Math.max(maxLeft, maxRight);
    }
}

2. 104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

Link: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

分析

分析二叉树的深度，也可以从底层向上推导。每当遇到一个节点，二叉树的深度就会加1，因此，我们可以构建一个函数，函数的返回值就是当当前节点为止，二叉树的最大深度，最大深度 = max(左子节点为根的树的最大深度, 右子节点为根的树的最大深度) + 1。根据该递推公式，从底向上进行遍历。

参考代码如下：

class Solution {

    // 使用后序遍历的方案来处理 -- 当前节点的深度 = max(左节点深度, 右节点深度) + 1;
    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;
    }
}

// java 代码一行实现
public int maxDepth(TreeNode root) {
    return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}