アルゴリズム練習ノート(八)——最大パスツリーを探す
1本の木の中で最大和の経路を探す
最初は私たちを惑わすかもしれません
しかし、その原理を見つけて、再帰を運用します.
巧みに表現できる!
タイトルアドレス:https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description
テーマ:Binary Tree Maximum Path Sum
説明:
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example: Given the below binary tree,
Return
回答:
参考解法中のO(n)の答えは、簡単に言えば、その原理を解析することであり、要するにmaxは最初は最小負数に設定され、木に負の値が存在することを防止し、アドレスを関数に伝達し、関数が各ノードを遍歴する際に、左サブツリーと右サブツリーにそのルートノードをリンクする最大経路を算出し、re値はこれまで遍歴したノードのうち、最大経路の値を表し、このように階層的に推進する.左サブツリー+右サブツリー+ルートのような特殊な場合を除けば,最大のパス値が得られる.
最初は私たちを惑わすかもしれません
しかし、その原理を見つけて、再帰を運用します.
巧みに表現できる!
タイトルアドレス:https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description
テーマ:Binary Tree Maximum Path Sum
説明:
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example: Given the below binary tree,
1
/ \
2 3
Return
6 . 回答:
class Solution {
public:
int maxToRoot(TreeNode*root, int& re){
if (!root) return 0;
int l = maxToRoot(root->left, re);
int r = maxToRoot(root->right, re);
if (l < 0) l = 0;
if (r < 0) r = 0;
if (l + r + root->val > re) re = l + r + root->val;
return root->val += max(l, r);
}
int maxPathSum(TreeNode* root) {
int max = -2147483648;
maxToRoot(root, max);
return max;
}
};参考解法中のO(n)の答えは、簡単に言えば、その原理を解析することであり、要するにmaxは最初は最小負数に設定され、木に負の値が存在することを防止し、アドレスを関数に伝達し、関数が各ノードを遍歴する際に、左サブツリーと右サブツリーにそのルートノードをリンクする最大経路を算出し、re値はこれまで遍歴したノードのうち、最大経路の値を表し、このように階層的に推進する.左サブツリー+右サブツリー+ルートのような特殊な場合を除けば,最大のパス値が得られる.