0%

[Leetcode]124. Binary Tree Maximum Path Sum(C++)

题目描述

题目链接:124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

例子

例子建议通过官方题目描述中察看二叉树的示例图方便理解结构

例子 1

Input: root = [1,2,3]
Output: 6

例子 2

Input: root = [-10,9,20,null,null,15,7]
Output: 42

Follow Up

Note

Constraints

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

解题思路

这道题关键是要理解题目中对路径的定义,理解对一个根节点有几种情况。理解之后再结合递归方法可以求解,题目中的路径的定义是可以是树中任意两个节点的通路,可以不通过根节点。并且题目中还隐含着一个意思,即每个节点只能通过 1 遍,意味着任意两个节点之间的通路只有一条。了解了题目的意思之后,我们来看一下对于一个根节点,满足条件的路径有几种情况:

  • 经过根节点
  • 不经过根节点,可以在左子树中或者右子树中

对于第二种情况,我们很容易想到可以通过递归的方式继续判断,那么可以继续深入考虑第一种情况,如果是要经过根节点的话,我们需要获取三个值,分别是:

  • 根节点的值
  • 左子树的最大的子路径和(注意这里的子路径表示该路径的其中一个端点必须是左子树根节点,否则不能和根节点连接)
  • 右子树的最大的子路径和(要求同上)

因此对递归函数(这里用 DFS 搜索),要做以下几件事情:

  • 计算左子树和右子树的最大子路径和
  • 计算经过当前根节点的最大路径和(根节点不一定是端点,可以同时取两侧子树最大路径和)并更新结果(这里的结果是最终要返回的结果)
  • 返回当前以根节点为端点的最大路径和(左子树和右子树的最大路径和只能选一个)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// @lc code=start
/**
* 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) {
result = INT_MIN;
dfs(root);
return result;
}

private:
int result;
int dfs(TreeNode* root) {
if (!root) return 0;

// max path sum that go through this node and its
// left & right subtree
int sum = root->val;

// max path sum that go through this node and one of its subtree
int left_path = root->val;
int right_path = root->val;

int left_sum = dfs(root->left);
if (left_sum > 0) {
sum += left_sum;
left_path += left_sum;
}

int right_sum = dfs(root->right);
if (right_sum > 0) {
sum += right_sum;
right_path += right_sum;
}

result = max(result, sum);
return max(left_path, right_path);
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h) — 递归深度

GitHub 代码同步地址: 124.BinaryTreeMaximumPathSum.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions