本文共 686 字,大约阅读时间需要 2 分钟。
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3]
1 / \ 2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ 9 20 / 15 7输出: 42
我的代码
static int x=[](){ std::ios::sync_with_stdio(false); cin.tie(NULL); return 0;}();int sum;int dfs(TreeNode* root){ if(root==NULL) return 0; else { int m=dfs(root->left); int n=dfs(root->right); int t=root->val; int temp_sum=max(t+m+n,max(t,max(t+m,t+n))); sum=max(sum,temp_sum); return max(t,max(t+m,t+n)); }}class Solution {public: int maxPathSum(TreeNode* root) { sum=INT_MIN; int b=dfs(root); return sum; }};
转载地址:http://ecnpz.baihongyu.com/