题目描述
题目链接: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 | // @lc code=start |
- 时间复杂度: O(n)
- 空间复杂度: O(h) — 递归深度
GitHub 代码同步地址: 124.BinaryTreeMaximumPathSum.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions