题解 | #二叉树的最大路径和#

题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点。
例如：给出以下的二叉树，返回的结果为6
示例1
输入：{-2,1}
返回值：1

题目分析

题目描述的路径可以从任意节点开始到任意节点结束，与之前必须要从根节点到叶子结点的路径不同，如下图，最大和的路径为2 -> 1 -> 3 -> 1。

遍历树的结点可以使用dfs，后序遍历。

解题思路

方法：后序遍历树结点，统计可以获得的最大路径和
思路过程：
1.从叶子结点开始遍历，计算从任意节点开始的路径和值 int cur = node.val;
2.对于结点的路径来说，可以往左子节点和右子节点延伸，left表示左子节点最大值, right表示右子节点最大值;
3.最后返回的值需要选择在此结点的值（加上左右最大值）和此点往左或右的路径最大值中选择更大的值： Math.max(cur, Math.max(root.val,Math.max(left, right) + root.val))。

代码实现

Java实现

    public int max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        backtrace(root);
        return max;
    }
    public int backtrace(TreeNode root){
        if(root == null) return 0;
        // 后序遍历，最后计算和，避免根节点值重复计算
        // 计算左、右子结点最大路径和
        int left = backtrace(root.left);
        int right = backtrace(root.right);
        int cur = root.val;
        if(left > 0){
            // 获取左子节点值
            cur += left;
        }
        if(right > 0){
            // 获取右子节点值
            cur += right;
        }
        // 统计出现的最大路径和
        max = Math.max(max, cur);
        // 返回当前最大路径和，不能直接返回cur，因为cur包含了两条路径，而返回只能一条路径
        return Math.max(root.val, Math.max(left, right) + root.val);
    }

时间复杂度：O(n)，n为树中所有的结点数量，遍历整个树消耗时间n；
空间复杂度：O(n)，递归栈最大的深度为n；

C++实现

    int maxPathSum(TreeNode *root) {
        // write code here
        dfs(root);
        return maxSum;
    }
    int dfs(TreeNode *root) {
        if (!root) return 0;
        // 获得左右子节点的最大路径和
        int left = dfs(root->left);
        int right = dfs(root->right);
        int current = root->val;
        // 当左右子节点值大于0时，当前值加上 左右子节点的值
        if (left > 0) current += left;
        if (right > 0) current += right;
        // 记录出现的最大值
        maxSum = max(maxSum, current);
         // 返回当前最大路径和，不能直接返回cur，因为cur包含了两条路径，而返回只能一条路径
        return max(root->val, max(left, right) + root->val);
    }
private:
    int maxSum = INT_MIN;

复杂度与Java实现相同。