分治，遞歸。 這道題有兩種好方法。
方法1：先有一個求深度depth的函數(shù)，然后遞歸比較各個節(jié)點的depth之差，返回結(jié)果。C++代碼：
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; } }; 方法2：深度優(yōu)先搜索根節(jié)點，遇到不合格的節(jié)點，及時反饋，這樣可以迅速得出結(jié)果，時間復(fù)雜度小。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: True if this Binary tree is Balanced, or false. */ bool isBalanced(TreeNode *root) { if (root == NULL) { return true; } if (dfs(root)>0) { return true; } return false; } int dfs(TreeNode * root) { if (root==NULL) { return 0; } int left = dfs(root->left); int right = dfs(root->right); if (left<0 || right<0 || abs(left-right)>1) { return -1; } return max(left,right) + 1; }};新聞熱點
疑難解答
