http://www.lintcode.com/en/problem/binary-tree-longest-consecutive-sequence-ii/\#

this problem is sort of similar except that the path can from left tree to right tree. and we need to know the maxUp and maxDown marking the direction

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the length of the longest consecutive sequence path
     */
    class ReturnType {
        int maxLen;
        int maxUp;
        int maxDown;
        public ReturnType(int maxLen, int maxUp, int maxDown) {
            this.maxLen = maxLen;
            this.maxUp = maxUp; //root.val == root.right - 1
            this.maxDown = maxDown; // root.val == root.rigth + 1
        }
    }
    public int longestConsecutive2(TreeNode root) {
        // Write your code here
        if (root == null) {
            return 0;
        }

        ReturnType ans = lc2Helper(root);
        return ans.maxLen;
    }

    public ReturnType lc2Helper(TreeNode root) {

        if (root == null) {
            return new ReturnType(0,0,0);
        }

        ReturnType left = lc2Helper(root.left);
        ReturnType right = lc2Helper(root.right);



        if (root.left == null && root.right == null) {
            return new ReturnType(1,1,1);
        }

        if (root.left == null) {
            if (root.val == root.right.val + 1) {
                return new ReturnType(Math.max(right.maxLen, right.maxDown + 1), 1, right.maxDown + 1);
            } else if (root.val == root.right.val - 1) {
                return new ReturnType(Math.max(right.maxLen, right.maxUp + 1), right.maxUp + 1, 1);
            }

            int maxLength = Math.max(1, right.maxLen);
            return new ReturnType(maxLength, 1, 1);

        }

        if (root.right == null) {
            if (root.val == root.left.val + 1) {
                return new ReturnType(Math.max(left.maxLen, left.maxDown + 1), 1, left.maxDown + 1);
            } else if (root.val == root.left.val - 1) {
                return new ReturnType(Math.max(left.maxLen, left.maxUp + 1), left.maxUp + 1, 1);
            }


            int maxLength = Math.max(1, left.maxLen);
            return new ReturnType(maxLength, 1, 1);
        }



        if (root.val == root.right.val + 1 && root.val == root.left.val - 1) {

            int maxLength = Math.max(left.maxUp + right.maxDown + 1, left.maxLen);
            maxLength = Math.max(maxLength, right.maxLen);
            return new ReturnType(maxLength, left.maxUp + 1, right.maxDown + 1);
        }

        if (root.val == root.right.val - 1 && root.val == root.left.val + 1) {
            int maxLength = Math.max(left.maxDown + right.maxUp + 1, left.maxLen);
            maxLength = Math.max(maxLength, right.maxLen);
            return new ReturnType(maxLength, right.maxUp + 1, left.maxDown + 1);
        }



        int leftMaxLength = left.maxLen;
        int rightMaxLength = right.maxLen;
        int leftMaxUp = 1;
        int leftMaxDown = 1;
        int rightMaxUp = 1;
        int rightMaxDown = 1;

        if (root.val == root.right.val + 1) {
            rightMaxLength = Math.max(right.maxDown + 1, left.maxLen);
            rightMaxLength = Math.max(rightMaxLength, right.maxLen);
            rightMaxDown = right.maxDown + 1;
        }

        if (root.val == root.right.val - 1) {
            rightMaxLength = Math.max(right.maxUp + 1, left.maxLen);
            rightMaxLength = Math.max(rightMaxLength, right.maxLen);
            rightMaxUp = right.maxUp + 1;
        }

        if (root.val == root.left.val + 1) {
            leftMaxLength = Math.max(left.maxDown + 1, left.maxLen);
            leftMaxLength = Math.max(leftMaxLength, right.maxLen);
            leftMaxDown = left.maxDown + 1;
        }

        if (root.val == root.left.val - 1) {
            leftMaxLength = Math.max(left.maxUp + 1, left.maxLen);
            leftMaxLength = Math.max(leftMaxLength, right.maxLen);
            leftMaxUp = left.maxUp + 1;
        }


        return new ReturnType(Math.max(leftMaxLength, rightMaxLength), Math.max(leftMaxUp, rightMaxUp), Math.max(leftMaxDown, rightMaxDown));

    }
}