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);
}
}
}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);
}
}