298. Binary Tree Longest Consecutive Sequence

Problem:

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,not3-2-1, so return 2.
4/20/2018 update:
不用全局变量的版本：
其实何全局变量区别不大，因为最后返回的值要比较count, left, right。 count其实是以当前node为结尾的sequence长度。老实说不好理解，还是不用全局变量好，在递归的过程中无脑比较max。

class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        return maxFrom(root, root.val, 0);
    }

    private int maxFrom(TreeNode root, int target, int count) {
        if (root == null) return 0;
        if (root.val == target) {
            count++;
        } else {
            count = 1;
        }
        int left = maxFrom(root.left, root.val + 1, count);
        int right= maxFrom(root.right, root.val + 1, count);
        return Math.max(count, Math.max(left, right));
    } 
}

2/25/2018 update:
A cleaner implementation is that follow the idea of path sum. Check whether current node value is equal to target (its parent's value  + 1).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = Integer.MIN_VALUE;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        maxFrom(root, 1, root.val + 1);
        return max;
    }
    
    private void maxFrom(TreeNode root, int count, int target) {
        if (root == null) return;
        if (root.val == target) count++; 
        else  count = 1;
        maxFrom(root.left, count, root.val + 1);
        maxFrom(root.right, count, root.val + 1);
        max = Math.max(count, max);
    }
}

Analysis:
Calc the temp length of left and right subtrees separately, then compare with the max.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        helper(root);
        return max;
    }
    public int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left) + 1;
        int right = helper(root.right) + 1;
        if (root.left != null && root.val + 1 != root.left.val) {
            left = 1;
        }
        if (root.right != null && root.val + 1 != root.right.val) {
            right = 1;
        }
        
        int len =  Math.max(left, right);
        max = Math.max(len, max);
        return len;
    }

}