124.Binary Tree Maximum Path Sum

tags: Hard,Tree,Binary Tree,DFS,DP

124. Binary Tree Maximum Path Sum

題目描述

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

範例

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10⁴].
• -1000 <= Node.val <= 1000

解答

C++

class Solution {
public:
    int dfs(TreeNode* node, int& ans) {
        if (!node) return 0;
        int L = max(0, dfs(node->left, ans));
        int R = max(0, dfs(node->right, ans));
        ans = max(ans, node->val + L + R);
        return max(L, R) + node->val;
    }
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        dfs(root, ans);
        return ans;
    }
};

Yen-Chi ChenSun, Dec 11, 2022

Python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node, ans):
            if not node: return 0
            L = max(dfs(node.left, ans), 0)
            R = max(dfs(node.right, ans), 0)
            ans[0] = max(ans[0], node.val + L + R)
            return node.val + max(L, R)
        ans = [float('-inf')]
        dfs(root, ans)
        return ans[0]

Yen-Chi ChenSun, Dec 11, 2022

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root: return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.ans = max(self.ans, max(root.val + left + right, root.val + left, root.val + right, root.val))
            return max(root.val, root.val + max(left, right))

        self.ans = -math.inf
        dfs(root)
        return self.ans

很容易一直 WA 的題目
KobeMon, Dec 12, 2022

C#

public class Solution {
    public int MaxPathSum(TreeNode root) {
        MaxPathSumFromRoot(root, out int maxSum);
        return maxSum;
    }

    private int MaxPathSumFromRoot(TreeNode node, out int maxPathSum) {
        if (node == null) {
            maxPathSum = int.MinValue;
            return 0;
        }

        int left = MaxPathSumFromRoot(node.left, out int leftMax);
        int right = MaxPathSumFromRoot(node.right, out int rightMax);
        
        maxPathSum = Max(node.val + left + right, leftMax, rightMax);

        return Max(node.val + Max(left, right), 0);
    }

    private int Max(params int[] numbers) {
        return Enumerable.Max(numbers);
    }
}

JimMon, Dec 12, 2022

Reference

回到題目列表