124. Binary Tree Maximum Path Sum

2019-11-08 19:45:28

字体：大中小

来源：转载

供稿：网友

这题一开始还以为那个忘记叫什么的算法，其实就是dfs，一开始在考虑的时候，对于每一个点出了考虑左右跟的最大，还多考虑了从其他地方到这个点的最大，其实这一个point是不用考虑的因为在递归的时候一定会经过相应的点（没想到。。。）

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int maxx; int findit(TreeNode* root){ if(root == NULL) return 0; int l = findit(root -> left); int r = findit(root -> right); if(l < 0) l = 0; if(r < 0) r = 0; if(r + l + root -> val > maxx) maxx = r + l + root -> val; return root -> val + max(r, l); } int maxPathSum(TreeNode* root) { maxx = INT_MIN; findit(root); return maxx; }};

上一篇：125. Valid Palindrome

下一篇：有关设计模式的体会