LeetCode 124. Binary Tree Maximum Path Sum

Question

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

Solution

• Solution1 – DFS, bottom up

class Solution {
    int maxvalue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxvalue;
    }
    public int dfs(TreeNode node){
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        left = left < 0 ? 0 : left;
        right = right < 0 ? 0 : right;
        maxvalue = Math.max(maxvalue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

bottom up general steps:
1. Base case
2. 向子问题要答案
3. 利用子问题构建当前答案
4. 额外操作
5. 返回答案给父问题

Complexity:

Time complexity: O(n)

Space complexity: O(n)