124. Binary Tree Maximum Path Sum
在一棵二元樹中，一條路徑是由一系列的節點組成的，其中每對相鄰的節點在路徑中有一條邊連接它們。一個節點在路徑中最多只能出現一次。注意，路徑不需要通過根節點。
路徑的路徑和是路徑中節點值的總和。
給定一棵二元樹的根節點，返回任何非空路徑的最大路徑和。
範例：
輸入：root = [1,2,3] 輸出：6 解釋：最佳路徑是 2 -> 1 -> 3，其路徑和為 2 + 1 + 3 = 6。
Python
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.max_sum = float('-inf')
self.dfs(root)
return self.max_sum
def dfs(self, node: Optional[TreeNode]) -> int:
if not node:
return 0
# Compute the maximum path sum with the left and right child nodes
left_max = max(self.dfs(node.left), 0) # only add if it's positive
right_max = max(self.dfs(node.right), 0) # only add if it's positive
# Update the global maximum path sum with the current node's value
# and the maximum sum from both children
current_max = node.val + left_max + right_max
self.max_sum = max(self.max_sum, current_max)
# Return the maximum path sum including the current node
return node.val + max(left_max, right_max)
21MB, 76ms
C++
#include <algorithm>
#include <climits>
using namespace std;
/**
* Definition for a binary tree node.
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
max_sum = INT_MIN;
dfs(root);
return max_sum;
}
private:
int max_sum;
int dfs(TreeNode* node) {
if (!node) return 0;
// Compute the maximum path sum with the left and right child nodes
int left_max = max(dfs(node->left), 0); // only add if it's positive
int right_max = max(dfs(node->right), 0); // only add if it's positive
// Update the global maximum path sum with the current node's value
// and the maximum sum from both children
int current_max = node->val + left_max + right_max;
max_sum = max(max_sum, current_max);
// Return the maximum path sum including the current node
return node->val + max(left_max, right_max);
}
};
26.17MB, 13ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val);
* this.left = (left === undefined ? null : left);
* this.right = (right === undefined ? null : right);
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
let maxSum = -Infinity;
const dfs = (node) => {
if (!node) {
return 0;
}
// Compute the maximum path sum with the left and right child nodes
let leftMax = Math.max(dfs(node.left), 0); // only add if it's positive
let rightMax = Math.max(dfs(node.right), 0); // only add if it's positive
// Update the global maximum path sum with the current node's value
// and the maximum sum from both children
let currentMax = node.val + leftMax + rightMax;
maxSum = Math.max(maxSum, currentMax);
// Return the maximum path sum including the current node
return node.val + Math.max(leftMax, rightMax);
};
dfs(root);
return maxSum;
};
58.63MB, 57ms
