Google
687 Longest Univalue Path

1. Question

Note: The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
1
5
2
/ \
3
4 5
4
/ \ \
5
1 1 5
Copied!
Output:
1
2
Copied!
Example 2:
Input:
1
1
2
/ \
3
4 5
4
/ \ \
5
4 4 5
Copied!
Output:
1
2
Copied!
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

2. Implementation

(1) DFS + Recursion
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public int longestUnivaluePath(TreeNode root) {
12
if (root == null) {
13
return 0;
14
}
15
16
int[] res = new int[1];
17
getLongestUnivaluePath(root, root.val, res);
18
return res[0];
19
}
20
21
public int getLongestUnivaluePath(TreeNode node, int val, int[] res) {
22
if (node == null) {
23
return 0;
24
}
25
26
int leftPath = getLongestUnivaluePath(node.left, node.val, res);
27
int rightPath = getLongestUnivaluePath(node.right, node.val, res);
28
29
res[0] = Math.max(res[0], leftPath + rightPath);
30
return val == node.val ? Math.max(leftPath, rightPath) + 1 : 0;
31
}
32
}
Copied!

3. Time & Space Complexity

DFS + Recursion: 时间复杂度O(n), 空间复杂度O(n)