Binary Tree Longest Consecutive Sequence II

Leave a comment

May 26, 2017 by oneOokay

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].


用recursion做. helper method 返回的是一个int[2]. 其中:

int[0]: 以当前node为根且以node为起点往儿子走的longest consecutive 递增的长度(node数量)

int[1]: 以当前node为根且以node为起点往儿子走的longest consecutive 递减的长度(node数量)

每一次recursion对于每个点的左右儿子分别求出这两个数值. 从而求得该点自己的Int[2].

同时对以该点的longest consecutive length更新max.

private int max;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        max = 0;
        helper(root);
        return max;
    }
    
    private int[] helper(TreeNode node){
        if (node == null) return new int[] {0, 0}; //空节点
        int inc = 1, dec = 1; //初始化为1
        int[] l = helper(node.left); 
        int[] r = helper(node.right);
        if (node.left != null){
//当前node到它的左儿子是递增的,所以当前node的inc为他儿子的inc + 1
            if (node.left.val == node.val + 1) inc += l[0];
//当前node到它的左儿子是递减的,所以当前node的dec为他儿子的dec + 1
            if (node.left.val == node.val - 1) dec += l[1];
        }
        
        if (node.right != null) {
//当前node到它的右儿子是递增的,所以当前node到它右儿子的inc为r[0] +1;
//对于当前node的总体的inc为之前计算的node到左儿子的inc和它到右儿子的inc的较大值.
            if (node.right.val == node.val + 1)
                inc = Math.max(inc, r[0] + 1);
            if (node.right.val == node.val - 1)
                dec = Math.max(dec, r[1] + 1);
        }
//总的longest consecutive length为当前node的inc + dec - 1
        max = Math.max(max, inc + dec - 1);
        return new int[]{inc, dec}; 
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: