首页 > 代码库 > 【leetcode】Binary Tree Maximum Path Sum (medium)
【leetcode】Binary Tree Maximum Path Sum (medium)
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
找树的最大路径和 注意路径可以从任意点起始和结束。
我发现我真的还挺擅长树的题目的，递归不难。就是因为有个需要比较的量（最大和），所以需要再写一个函数。
因为路径可以从任意点起始和结束，所以每次递归的时候左右子树小于等于0的就可以不管了。
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;//Definition for binary treestruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public: int maxPathSum(TreeNode *root){ if(root == NULL) { return 0; } int MaxPathSum = root->val; //赋的初值一定要小于等于最后的值 maxPathSumCur(root, MaxPathSum); return MaxPathSum; } int maxPathSumCur(TreeNode *root, int& MaxPathSum) { if(root == NULL) { return 0; } int lsum = maxPathSumCur(root->left, MaxPathSum); int rsum = maxPathSumCur(root->right, MaxPathSum); int maxPathSumCurrent = root->val; //每次根的值一定要加上 左右子树的就加大于0的 if(lsum > 0) { maxPathSumCurrent += lsum; } if(rsum > 0) { maxPathSumCurrent += rsum; } MaxPathSum = max(maxPathSumCurrent, MaxPathSum); return max(root->val, max(root->val + lsum, root->val +rsum)); //返回时返回根 节点加左 或右子树 或单独根节点中最大的 } void create(TreeNode *& root) { int d; scanf("%d", &d); if(d != 0) { root = new TreeNode(d); create(root->left); create(root->right); } }};int main(){ Solution s; TreeNode * T = NULL; s.create(T); int sum = s.maxPathSum(T); return 0;}
【leetcode】Binary Tree Maximum Path Sum (medium)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。