分治，動態(tài)規(guī)劃。
分析：最長的路徑一定經(jīng)過某一個點，并且以這一個點為根節(jié)點；所以可以動態(tài)遍歷每一個節(jié)點，找到使路徑和最大的根節(jié)點。C++代碼：
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */class Solution {public: /** * @param root: The root of binary tree. * @return: An integer */ int maxPathSum(TreeNode *root) { if (root == NULL) { return 0; } vector<int> res; maxRoot(root,res); int a = res[0]; for(auto i : res){ if (i > a) { a = i; } } return a; } void maxRoot(TreeNode * root, vector<int> &res) { if (root == NULL ) { return; } int l = maxLink(root->left); int r = maxLink(root->right); res.push_back(max(0,l) + max(0,r) + root->val); maxRoot(root->left,res); maxRoot(root->right,res); } int maxLink(TreeNode * root) { if (root == NULL) { return 0; } return root->val + max(0,max(maxLink(root->left),maxLink(root->right))); }};看網(wǎng)友的更簡潔的方法：
在一個函數(shù)的不斷遞歸中處理了最后的最大值ret，還要在最后返回一root為根節(jié)點的最大的一邊值。class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxPathSum(TreeNode *root) { // write your code here int ret = INT_MIN; onePath(root,ret); return ret; } int onePath(TreeNode* root,int&ret) { if(root==nullptr) return 0; int l = onePath(root->left,ret); int r = onePath(root->right,ret); ret = max(ret,max(0,l)+max(0,r)+root->val); return max(0,max(l,r))+root->val; } };新聞熱點
疑難解答
