木

最長の単一値パス[数値の最長パス]



Longest Univalue Path



問題：

二分木が与えられた場合、パス内の各ノードが同じ値を持つ最長のパスの長さを見つけます。このパスは、ルートを通過する場合と通過しない場合があります。



注意：2つのノード間のパスの長さは、ノード間のエッジの数で表されます。

例1：



入力：

class Solution { public: int longestUnivaluePath(TreeNode* root) { int lup = 0 if (root) dfs(root, lup) return lup } private: int dfs(TreeNode* node, int& lup) { //lup: the longest path in the tree with node as the root node int l = node->left? dfs(node->left, lup): 0 //l: the longest path of the left subtree from the root node//Note: not necessarily the longest path of the left subtree/ /lup: update to the longest path of the left subtree int r = node->right? dfs(node->right, lup): 0 //r: the longest path of the right subtree from the root node//Note: not necessarily the longest path of the right subtree/ /lup: update to the longest path in the left and right subtrees int resl = node->left && node->left->val == node->val ? l + 1 : 0 int resr = node->right && node->right->val == node->val ? r + 1 : 0 lup = max(lup, resl + resr) //lup: updated to be the longest path in the tree with node as the root node //Note: the path is the number of edges, not the number of nodes return max(resl, resr) //The longest path from the root node } }

出力：

 5 /  4 5 /   1 1 5

例2：



入力：

2

出力：

 1 /  4 5 /   4 4 5

注意：指定された二分木には、10000個以下のノードがあります。木の高さは1000以下です。

解決する： 

2