LeetCode——二叉树中的最大路径和

NO.124 二叉树中的最大路径和 困难

本题是 NO.112 路径总和 与 NO.113 路径总和 II 的又一个升级版，本题不再是从根到叶子，而是任意路径。

思路一：深搜 二叉树具有递归性，自然就会想到递归求左子树最大路径和 与 右子树最大路径和，然后再求整个树/子树的路径和。以求解某个子树的路径和为例：

这个总的子树最终返回的最大路径和可能是：a+b+子树根 或者 a+子树根+子树根的父节点 或者b+子树根+子树根的父节点

最终的结果最小是0，不需要任何一个节点值加入路径和；如果路径和是负数，则舍弃。

int max = Integer.MIN_VALUE;

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

private int dfs(TreeNode root) {
    if (root == null) return 0;
    //求左右子树的路径和
    int left = dfs(root.left);
    int right = dfs(root.right);
    //如果路径和是负数，则舍弃掉这条路径
    if (left < 0) {
        left = 0;
    }
    if (right < 0) {
        right = 0;
    }
    //更新max
    max = Math.max(max, left + right + root.val);
    //返回子树最大的路径和
    return Math.max(left, right) + root.val;
}

时间复杂度：O(n) 遍历

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github