Star

LeetCode 298. Binary Tree Longest Consecutive Sequence

Posted on | In |

Question:

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). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
For example,
   1
    \
     3
    / \
   2   4
        \
         5
Longest consecutive sequence path is 3-4-5, so return 3.
   2
    \
     3
    /
   2
  /
 1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

Explanation:

递归。想清楚base case和递归的模式即可。左右值，以及当前值，不要混淆。

Code:

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
39
40
41
42
Solution 1:
public class Solution {
    public int longestConsecutive(TreeNode root) {
        return (root==null)?0:Math.max(Helper(root.left,1,root.val), Helper(root.right, 1, root.val));
    }
    public int Helper(TreeNode root, int count, int val) {
        if (root == null) return count;
        count = (root.val - val == 1) ? count+1:1;
        int leftCount = Helper(root.left, count, root.val);
        int rightCount = Helper(root.right, count, root.val);
        return Math.max(count, Math.max(leftCount, rightCount));
    }
}
Solution 2:
public class Solution {
    int max;
    public int longestConsecutive(TreeNode root) {
        max = 0;
        helper(root);
        return max;
    }
    public int helper(TreeNode root){
        int subMax = 1;
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (root.left != null && root.val + 1==root.left.val) subMax = Math.max(subMax, left+1);
        if (root.right != null && root.val + 1 == root.right.val) subMax = Math.max(subMax, right+1);
        if (subMax > max) {
            max = subMax;
        }
        return subMax;
    }
}