Binary Tree Longest Consecutive Sequence

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
   
    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, not 3-2-1, so return 2.

分析

这种题思路比较直接，就是维护一个最大值，DFS遍历整个树，不断更新最大值。函数里可以包含父节点的值及当前连续长度，如果发现本身值跟父节点值不连续，当前连续长度变为1，否则增加当前连续长度。

当然，这道题也可以要求返回的不是长度，而是连续的数字。只要在原来代码基础上再增加一个tail变量即可，每次更新max时，也更新tail，这样最后可以更具tail值即连续序列最后一个数字的值及整个序列长度构造出整个连续序列。

复杂度

time: O(n), space: O(h)

代码

public class Solution {
    public int longestConsecutive(TreeNode root) {
        int[] max = {0};
        helper(root, Integer.MIN_VALUE, 0, max);
        return max[0];
    }
    
    private void helper(TreeNode node, int prev, int curr, int[] max) {
        if (node == null) 
            return;
            
        // 与父节点值连续，当前连续长度自增，否则恢复成1
        if (node.val == prev + 1) 
            curr++;
        else 
            curr = 1;
            
        // 更新最大值    
        max[0] = Math.max(max[0], cur);
        helper(node.left, node.val, curr, max);
        helper(node.right, node.val, curr, max);
    }
}