0124. 二叉树中的最大路径和
题目地址(124. 二叉树中的最大路径和)
题目描述
1
给定一个非空二叉树，返回其最大路径和。
2
3
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
4
5
示例 1：
6
7
输入：[1,2,3]
8
9
1
10
/ \
11
2 3
12
13
输出：6
14
示例 2：
15
16
输入：[-10,9,20,null,null,15,7]
17
18
-10
19
/ \
20
9 20
21
/ \
22
15 7
23
24
输出：42
Copied!
前置知识
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这道题目的 path 让我误解了，然后浪费了很多时间来解这道题。我觉得 leetcode 给的 demo 太少了，不足以让我理解 path 的概念因此我这里自己画了一个图，来补充一下，帮助大家理解 path 的概念，不要像我一样理解错啦。
首先是官网给的两个例子：
124.binary-tree-maximum-path-sum
接着是我自己画的一个例子：
124.binary-tree-maximum-path-sum
如图红色的部分是最大路径上的节点。大家可以结合上面的 demo 来继续理解一下 path， 除非你理解了 path，否则不要往下看。
树的题目，基本都是考察递归思想的。因此我们需要思考如何去定义我们的递归函数，在这里我定义了一个递归函数，它的功能是，
返回以当前节点为根节点的MaxPath但是有两个条件:
- 1.根节点必须选择
- 2.左右子树只能选择一个
为什么要有这两个条件?
我的想法是原问题可以转化为：以每一个节点为根节点，分别求出 MaxPath，最后计算最大值，因此第一个条件需要满足.
对于第二个条件，由于递归函数子节点的返回值会被父节点使用，因此我们如果两个孩子都选择了就不符合 MaxPath 的定义了。实际上这道题，当遍历到某一个节点的时候，我们需要子节点的信息，然后同时结合自身的 val 来决定要不要选取左右子树以及选取的话要选哪一个， 因此这个过程本质上就是
后序遍历基本算法就是不断调用递归函数，然后在调用过程中不断计算和更新 MaxPath，最后在主函数中将 MaxPath 返回即可。
关键点解析
- 递归
- 理解题目中的 path 定义
代码
代码支持：JavaScript，Java，Python, CPP
- JavaScript
1
/*
2
* @lc app=leetcode id=124 lang=javascript
3
*
4
* [124] Binary Tree Maximum Path Sum
5
*/
6
/**
7
* Definition for a binary tree node.
8
* function TreeNode(val) {
9
* this.val = val;
10
* this.left = this.right = null;
11
* }
12
*/
13
function helper(node, payload) {
14
if (node === null) return 0;
15
16
const l = helper(node.left, payload);
17
const r = helper(node.right, payload);
18
19
payload.max = Math.max(
20
node.val + Math.max(0, l) + Math.max(0, r),
21
payload.max
22
);
23
24
return node.val + Math.max(l, r, 0);
25
}
26
/**
27
* @param {TreeNode} root
28
* @return {number}
29
*/
30
var maxPathSum = function (root) {
31
if (root === null) return 0;
32
const payload = {
33
max: root.val,
34
};
35
helper(root, payload);
36
return payload.max;
37
};
Copied!
- Java
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
int ans;
12
public int maxPathSum(TreeNode root) {
13
ans = Integer.MIN_VALUE;
14
helper(root); // recursion
15
return ans;
16
}
17
18
public int helper(TreeNode root) {
19
if (root == null) return 0;
20
int leftMax = Math.max(0, helper(root.left)); // find the max sub-path sum in left sub-tree
21
int rightMax = Math.max(0, helper(root.right)); // find the max sub-path sum in right sub-tree
22
ans = Math.max(ans, leftMax+rightMax+root.val); // find the max path sum at current node
23
return max(leftMax, rightMax) + root.val; // according to the definition of path, the return value of current node can only be that the sum of current node value plus either left or right max path sum.
24
}
25
}
Copied!
- Python
1
class Solution:
2
ans = float('-inf')
3
def maxPathSum(self, root: TreeNode) -> int:
4
def helper(node):
5
if not node: return 0
6
l = helper(node.left)
7
r = helper(node.right)
8
self.ans = max(self.ans, max(l,0) + max(r, 0) + node.val)
9
return max(l, r, 0) + node.val
10
helper(root)
11
return self.ans
Copied!
- CPP
1
class Solution {
2
private:
3
int ans = INT_MIN;
4
int postOrder(TreeNode *root) {
5
if (!root) return INT_MIN;
6
int L = max(0, postOrder(root->left)), R = max(0, postOrder(root->right));
7
ans = max(ans, L + R + root->val);
8
return root->val + max(L, R);
9
}
10
public:
11
int maxPathSum(TreeNode* root) {
12
postOrder(root);
13
return ans;
14
}
15
};
Copied!
复杂度分析
- 时间复杂度：$O(n)$，其中 n 为节点数。
- 空间复杂度：$O(h)$， 其中 h 为树高。
相关题目
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 1yr ago