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

Problem: 124. 二叉树中的最大路径和

思路

用dp的思想，遍历这个树，dfs函数返回当前子树的最大路径和，如果最大路径和为负数则不途径这个子树，设为0。同时在dfs遍历的时候，以左右子树分别最大路径和加上当前结点的值尝试更新答案，因为左右子树的最大路径和都是非负的。

显然在这个过程中，我们是可以遍历树上所有结点的。

踩坑

一开始看到路径和，我想到的是把树看成图来解，想到了枚举所有叶子到叶子的路径，然后对单条路径用dp的思想求最大值，但是这样显然是$O(n^2)$算法，会超时。

后来舍友的想法给了我提醒，同样是使用dp的思想，但是用树的遍历来做。这样是对的，树的题目还是得用树的遍历才能最大程度地利用其性质。

复杂度

• 时间复杂度: $O(n)$，n为节点数目。
• 空间复杂度: $O(n)$，递归深度，最坏情况下为一条链。

Code

class Solution {
    public int max = -1001;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int leftVal = dfs(root.left);
        int rightVal = dfs(root.right);
        max = Math.max(leftVal + rightVal + root.val, max);
        return Math.max(Math.max(leftVal + root.val, rightVal + root.val), 0);
    }
}