124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
是路径中各节点值的总和。
给你一个二叉树的根节点 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 * 104]
-1000 <= Node.val <= 1000
递归
任何路径,必定有且一个节点是路径所有节点的祖先,我们可以枚举路径的祖先节点。故时间复杂度是O(n)。
对于Do函数只考虑本节点及其子孙,不考虑其祖先。
iLeafDirMaxSum | 以root为起点的最大路径和,必定包括root节点,如果左支或右支的iLeafDirMaxSum较大者为正,则加上。 |
iRet | 以root为根的最大路径和,必定包括root节点,如果左支(右支)iLeafDirMaxSum为正,则加上 |
代码
核心代码
class Solution {
public:
int maxPathSum(TreeNode* root) {
Do(root);
return m_iRet;
}
int Do(TreeNode* root)
{
if (nullptr == root)
{
return 0;
}
const int left = Do(root->left);
const int right = Do(root->right);
int iRet = root->val;
if (left >= 0)
{
iRet += left;
}
if (right >= 0)
{
iRet += right;
}
m_iRet = max(iRet, m_iRet);
std::cout << "root:" << root->val << " ret " << iRet << std::endl;
int iLeafDirMaxSum = root->val;
const int iMax = max(left, right);
if (iMax >= 0)
{
iLeafDirMaxSum += iMax;
}
return iLeafDirMaxSum;
}
int m_iRet = -10000'0000;
};
测试用例
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, int iLeft) : val(x), left(new TreeNode(iLeft)), right(nullptr) {}
TreeNode(int x, int iLeft, int iRghit) : val(x), left(new TreeNode(iLeft)), right(new TreeNode(iRghit)) {}
};
namespace NTree
{
TreeNode* Init(const vector<int>& nums, int iNull = 10000)
{
if (0 == nums.size())
{
return nullptr;
}
vector<TreeNode*> ptrs(nums.size() + 1), ptrParent(1);
for (int i = 0; i < nums.size(); i++)
{
if (iNull == nums[i])
{
continue;
}
const int iNO = i + 1;
ptrs[iNO] = new TreeNode(nums[i]);
ptrParent.emplace_back(ptrs[iNO]);
if (1 == iNO)
{
continue;
}
if (iNO & 1)
{//奇数是右支
ptrParent[iNO / 2]->right = ptrs[iNO];
}
else
{
ptrParent[iNO / 2]->left = ptrs[iNO];
}
}
return ptrs[1];
}
}
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s,t;
const int null = -10000;
{
Solution sln;
vector<int> nums = { 1,2,3 };
auto root = NTree::Init(nums, null);
auto res = sln.maxPathSum(root);
Assert(6, res);
}
{
Solution sln;
vector<int> nums = { -10,9,20,null,null,15,7 };
auto root = NTree::Init(nums, null);
auto res = sln.maxPathSum(root);
Assert(42, res);
}
}
2023年1月代码
/**
- 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) {
Sum(root);
return m_iRet;
}
int Sum(TreeNode* node)
{
if (nullptr == node)
{
return 0;
}
std::multiset setLeftRight;
setLeftRight.insert(Sum(node->left));
setLeftRight.insert(Sum(node->right));
if (*setLeftRight.begin() > 0)
{
m_iRet = max(m_iRet, node->val + *setLeftRight.begin() + *setLeftRight.rbegin());
}
if (*setLeftRight.rbegin() > 0)
{
m_iRet = max(m_iRet, node->val + *setLeftRight.rbegin());
return node->val + setLeftRight.rbegin();
}
m_iRet = max(m_iRet, node->val);
return node->val;
}
int m_iRet = INT_MIN;
std::unordered_map<TreeNode, std::set> m_mapTop2Dis;
};