[LintCode] Problem 614 - Binary Tree Longest Consecutive Sequence II

Posted on | In ,

Given a binary tree, find the length(number of nodes) of the longest consecutive sequence(Monotonic and adjacent node values differ by 1) path.
The path could be start and end at any node in the tree

Example

No.1

Input:
{1,2,0,3}

Output:
4

Explanation:

1
2
3
4
5
    1
   / \
  2   0
 /
3

0-1-2-3

No.2

Input:
{3,2,2}

Output:
2

Explanation:

1
2
3
  3
 / \
2   2

2-3

Code

1
2
3
4
5
6
7
8
public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
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
public class ResultType {
    private int increase;
    private int decrease;
    public ResultType(int increase, int decrease) {
        this.increase = increase;
        this.decrease = decrease;
    }
}

private int max = 0;

public int longestConsecutive2(TreeNode root) {
    dfs(root, null);
    return max;
}

private ResultType dfs(TreeNode root, TreeNode parent) {
    if (root == null)
        return new ResultType(0, 0);

    ResultType left = dfs(root.left, root);
    ResultType right = dfs(root.right, root);

    max = Math.max(max, left.increase + right.decrease + 1);
    max = Math.max(max, left.decrease + right.increase + 1);

    int increase = 0;
    int decrease = 0;

    if (parent == null || root.val + 1 == parent.val)
        decrease = Math.max(left.decrease, right.decrease) + 1;
    else if (parent == null || root.val - 1 == parent.val)
        increase = Math.max(left.increase, right.increase) + 1;

    return new ResultType(increase, decrease);
}