ツリー内の最大パスと
3744 ワード
分治、動的計画.分析:最長の経路は必ずある点を通過し、この点をルートノードとする.したがって、各ノードを動的に巡回し、パスと最大のルートノードを見つけることができます.
C++コード:
ネットユーザーのより簡潔な方法を見る:は、1つの関数の継続的な再帰において最後の最大値retを処理し、最後にrootがルートノードの最大の側値であることを返す.
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)));
}
};ネットユーザーのより簡潔な方法を見る:
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;
}
};