LeetCode 解題紀錄 124. Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum - LeetCode

題目

在一個 Binary Tree 中返回最大的 Path sum

限制

• node數目 [1,3*10⁴]
• -1000 ≤ node.val ≤ 1000

觀察

• 可以形成 path 的可能性有
• node.val
• node.val + left path
• node.val + right path
• node.val + left path + right path
• 在每個 node 檢查最大的 path sum

解法 1 (Post order DFS)

• 使用 DFS 遍覽每個節點，並紀錄最大的 path sum
• 要記得遞迴返回的是單一路徑，因此要移除 node.val + left path sum + right path sum可能形成的最大值

class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        max = -10000;
        dfs(root);
        return max;
    }

    int dfs(TreeNode root) {
        if(root == null)
            return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int pathSum = Math.max(root.val,Math.max(left+root.val, right+root.val));
        max = Math.max(max, Math.max(pathSum, root.val+left+right));
        return pathSum;
    }
}

結果

TC：O(n)， SC：O(h) h 是 binary tree 的高度