【算法题】二叉树中的最大路径和

这题说的是找出二叉树的最大路径和，这里的最大路径不一定经过根节点，所以我们可以采用自下往上的遍历方式来计算， 对于当前节点：

• 如果它的两个子节点路径都是负的，就没必要选择了，因为如果是负数，越选择和就会越小，如下图中的第 1 种情况。
• 如果它的两个子节点路径一个是正的，一个是负的，我们只需要选择正的即可，如下图中的第 2 种情况。
• 如果它的两个子节点都是正的，我们可以都选择，也可以选择其中的一个子节点，如下图中的第 3 种情况。

最后我们只需要保存选择的最大值即可，对于第 1 ，2 两种情况，我们还可以接着往上继续选择，但对于第 3 种情况，如果两个子节点都选择了，就不能再往上选了，分支会出现分叉。

    private int ans = Integer.MIN_VALUE;// 默认个给个最小值

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode root) {
        if (root == null)
            return 0;
        int left = dfs(root.left);// 左子节点的值
        int right = dfs(root.right); // 右子节点的值
        // 第1,2种情况，左右子节点最多只能选择一个
        int res = root.val + Math.max(0, Math.max(left, right));
        // 第3种情况，左右子节点可以都选择。
        int cur = root.val + Math.max(0, left) + Math.max(0, right);
        // 记录最大值
        ans = Math.max(ans, Math.max(cur, res));
        // 第1,2种情况还可以再计算，所以返回的是res
        return res;
    }

    int ans = INT_MIN;// 默认个给个最小值

public:
    int maxPathSum(TreeNode *root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left);// 左子节点的值
        int right = dfs(root->right); // 右子节点的值
        // 第1,2种情况，左右子节点最多只能选择一个
        int res = root->val + max(0, max(left, right));
        // 第3种情况，左右子节点可以都选择。
        int cur = root->val + max(0, left) + max(0, right);
        // 记录最大值
        ans = max(ans, max(cur, res));
        // 第1,2种情况还可以再计算，所以返回的是res
        return res;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》