687 Longest Univalue Path

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)

465 Optimal Account Balancing

543 Diameter of Binary Tree

Last modified 2yr ago

Copy link

Contents

687. Longest Univalue Path

1. Question

2. Implementation

3. Time & Space Complexity

687. Longest Univalue Path​

1. Question

2. Implementation

3. Time & Space Complexity

687. Longest Univalue Path