LeetCode 124 Binary Tree Maximum Path Sum
LeetCode 124 Binary Tree Maximum Path Sum
ShenduCC
发布于 2018-07-24 16:08:14
发布于 2018-07-24 16:08:14
题目链接：
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes 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.
dfs 深度遍历
遍历的时候，记录根节点到左子树和右子树中的某个点的最大距离，再比较下即可
class Solution {
public:
int ans = -99999999;
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root)
{
if(root->left==NULL&&root->right==NULL)
{ ans=max(ans,root->val);return root->val;}
if(root->left!=NULL&&root->right==NULL)
{
int xleft = dfs(root->left);
ans = max(ans,max(root->val+xleft,root->val));
return max(root->val+xleft,root->val);
}
if(root->left==NULL&&root->right!=NULL)
{
int xright = dfs(root->right);
ans = max(ans,max(root->val,root->val+xright));
return max(root->val,root->val+xright);
}
if(root->left!=NULL&&root->right!=NULL)
{
int xleft = dfs(root->left);
int xright = dfs(root->right);
ans = max(ans,max(root->val,max(root->val+xleft,max(root->val+xleft+xright,root->val+xright))));
return max(root->val,max(root->val+xleft,root->val+xright));
}
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读