124. 二叉树中的最大路径和(Binary Tree Maximum Path Sum)H
英文题目
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 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 * 104].
1000 <= Node.val <= 1000
中文题目
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
输入:root = [1,2,3] 输出:6 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7] 输出:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
提示:
树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000
递归
递归内其实是后序遍历,其返回值是根节点加上最大值的左/右子树节点和
题目要求的是最大路径和,有三种情况
a / \ b c
1.b+a+c,是代码中的lmr
2.b+a+a的父节点
3.c+a+a的父节点
2和3可合并起来,即 max(b,c) + a + a的父节点,
需注意的是,节点有可能是负值,最大和要想办法舍弃负值
然后每一次都把最大值保存起来
但返回的是根节点加上最大值的左/右子树的节点和
时间复杂度O(N),空间复杂度(N)
# python3: 时间 76 ms, 击败 88.52%; 内存 24.4 MB, 击败 32.24% # 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.res = float('-inf') self.dfs(root) return self.res def dfs(self, root: Optional[TreeNode]) -> int: if not root: return 0 left = max(self.dfs(root.left), 0) right = max(self.dfs(root.right), 0) lmr = root.val + left + right self.res = max(self.res, lmr) return root.val + max(left, right)
// c++: 时间 12 ms, 击败 99.49%; 内存 27 MB, 击败 41.94% /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxPathSum(TreeNode* root) { int res = numeric_limits<int>::lowest(); dfs(res, root); return res; } int dfs(int & res, TreeNode* root) { if (root == nullptr) { return 0; } int left = max(dfs(res, root->left), 0); int right = max(dfs(res, root->right), 0); int lmr = root->val + left + right; res = max(res, lmr); return root->val + max(left, right);; } };
// java: 时间 0 ms, 击败 100%; 内存 42.6 MB, 击败 73.64% /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return res; } private int dfs(TreeNode root) { if (root == null) { return 0; } int left = Math.max(dfs(root.left), 0); int right = Math.max(dfs(root.right), 0); int lmr = root.val + left + right; res = Math.max(res, lmr); return root.val + Math.max(left, right); } }
// go: 时间 12 ms, 击败 91.92%; 内存 6.9 MB, 击败 66.54% /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxPathSum(root *TreeNode) int { res := math.MinInt dfs(&res, root) return res } func dfs(res *int, root *TreeNode) int { if root == nil { return 0 } left := MaxInt(dfs(res, root.Left), 0) right := MaxInt(dfs(res, root.Right), 0) lmr := root.Val + left + right *res = MaxInt(*res, lmr) return root.Val + MaxInt(left, right) } func MaxInt(x, y int) int { if x > y { return x } return y }
// javascript: 时间 80 ms, 击败 54.78%; 内存 50.3 MB, 击败 74.77% /** * 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 res = Number.MIN_SAFE_INTEGER; const dfs = function(root) { if (root == null) { return 0; } let left = Math.max(dfs(root.left), 0); let right = Math.max(dfs(root.right), 0); let lmr = root.val + left + right; res = Math.max(res, lmr); return root.val + Math.max(left, right); }; dfs(root); return res; };