Java
-
/** Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. Note: The length of path between two nodes is represented by the number of edges between them. Example 1: Input: 5 / \ 4 5 / \ \ 1 1 5 Output: 2 Example 2: Input: 1 / \ 4 5 / \ \ 4 4 5 Output: 2 Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000. */ public class Longest_Univalue_Path { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int longest = 0; public int longestUnivaluePath(TreeNode root) { if (root == null) { return 0; } dfs(root); return longest; } private int dfs(TreeNode root) { if (root == null) { return 0; } int leftLeaf = dfs(root.left); int rightLeaf = dfs(root.right); int leftCount = 0; int rightCount = 0; if (root.left != null && root.left.val == root.val) { leftCount = 1 + leftLeaf; } if (root.right != null && root.right.val == root.val) { rightCount = 1 + rightLeaf; } int total = leftCount + rightCount; // here is edge, not node count longest = Math.max(longest, total); return Math.max(leftCount, rightCount); } } }
-
// OJ: https://leetcode.com/problems/longest-univalue-path/ // Time: O(N) // Space: O(H) class Solution { int ans = 0; int dfs(TreeNode *root) { if (!root) return 0; int left = dfs(root->left), right = dfs(root->right); if (!root->left || root->left->val != root->val) left = 0; if (!root->right || root->right->val != root->val) right = 0; ans = max(ans, 1 + left + right); return 1 + max(left, right); } public: int longestUnivaluePath(TreeNode* root) { dfs(root); return max(0, ans - 1); } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def longestUnivaluePath(self, root): """ :type root: TreeNode :rtype: int """ longest = [0] def dfs(root): if not root: return 0 left_len, right_len = dfs(root.left), dfs(root.right) left = left_len + 1 if root.left and root.left.val == root.val else 0 right = right_len + 1 if root.right and root.right.val == root.val else 0 longest[0] = max(longest[0], left + right) return max(left, right) dfs(root) return longest[0]
Java
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int ans; public int longestUnivaluePath(TreeNode root) { ans = 0; arrowLength(root); return ans; } public int arrowLength(TreeNode node) { if (node == null) return 0; int left = arrowLength(node.left); int right = arrowLength(node.right); int arrowLeft = 0, arrowRight = 0; if (node.left != null && node.left.val == node.val) arrowLeft += left + 1; if (node.right != null && node.right.val == node.val) arrowRight += right + 1; ans = Math.max(ans, arrowLeft + arrowRight); return Math.max(arrowLeft, arrowRight); } }
-
// OJ: https://leetcode.com/problems/longest-univalue-path/ // Time: O(N) // Space: O(H) class Solution { int ans = 0; int dfs(TreeNode *root) { if (!root) return 0; int left = dfs(root->left), right = dfs(root->right); if (!root->left || root->left->val != root->val) left = 0; if (!root->right || root->right->val != root->val) right = 0; ans = max(ans, 1 + left + right); return 1 + max(left, right); } public: int longestUnivaluePath(TreeNode* root) { dfs(root); return max(0, ans - 1); } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def longestUnivaluePath(self, root): """ :type root: TreeNode :rtype: int """ longest = [0] def dfs(root): if not root: return 0 left_len, right_len = dfs(root.left), dfs(root.right) left = left_len + 1 if root.left and root.left.val == root.val else 0 right = right_len + 1 if root.right and root.right.val == root.val else 0 longest[0] = max(longest[0], left + right) return max(left, right) dfs(root) return longest[0]