Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

1
2
3
4
5
6
7
1
 \
  3
 / \
2   4
     \
      5

Longest consecutive sequence path is 3-4-5, so return 3.

1
2
3
4
5
6
7
  2
   \
    3
   / 
  2    
 / 
1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

Traverse

这种方式主要是用一个全局变量来记录max.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int max = 1;
public int longestConsecutive(TreeNode root) {
    if (root == null)
        return 0;
    helper(root);
    return max;
}
// return the length of the longest consecutive sequence including the root
public int helper(TreeNode root) {
    if (root == null)
        return 0;
    int left = helper(root.left);
    int right = helper(root.right);
    int ans = 1;
    if (root.left != null && root.val == root.left.val - 1) {
        ans = left + 1;
    }
    if (root.right != null && root.val == root.right.val - 1) {
        ans = Math.max(ans, right + 1);
    }
    max = Math.max(max, ans);
    return ans;
}

Divide & Conquer

这种写法更加通用一些, ResultType可以记录的东西可以很多.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class ResultType {
    // the global max length
    int max = 0;
    // the max length include the root
    int length = 0;
    public ResultType(int max, int length) {
        this.max = max;
        this.length = length;
    }
}
public int longestConsecutive(TreeNode root) {
    return helper(root).max;
}
public ResultType helper(TreeNode root) {
    if (root == null)
        return new ResultType(0, 0);
    ResultType left = helper(root.left);
    ResultType right = helper(root.right);
    int max = Math.max(left.max, right.max);
    int length = 1;
    if (root.left != null && root.val == root.left.val - 1) {
        length = left.length + 1;
    }
    if (root.right != null && root.val == root.right.val - 1) {
        length = Math.max(length, right.length + 1);
    }
    max = Math.max(length, max);
    return new ResultType(max, length);
}

Follow up

论坛里有人说是”如果tree很大怎么存”, 这个问题感觉有点莫名其妙.

假装是要考分布式吧, tree当然要存在文本文件里, 可以存成一个数组. 然后用ResultType那个方法可以更好的分布式处理