Problem

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

思路(traverse + divide & conquer)

1. 因为路径可以是increasing或者decreasing, 所以from bottom to up, 我们需要传递两个值up 和 down
2. 通过左子树和右子树的up和down构造父节点的up和down, 并且和全局变量比较, 然后更新和返回.

    public int longestConsecutive(TreeNode root) {
        longest = 0;
        helper(root);
        return longest;
    }

    private int longest;

    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0);
        }

        Result left = helper(root.left);
        Result right = helper(root.right);

        int up = 0;
        int down = 0;

        int leftUp = 0;
        int rightUp = 0;
        int leftDown = 0;
        int rightDown = 0;

        if (root.left != null && root.left.val + 1 == root.val) {
            leftUp = left.up;
        }

        if (root.right != null && root.right.val + 1 == root.val) {
            rightUp = right.up;
        }

        if (root.left != null && root.left.val - 1 == root.val) {
            leftDown = left.down;
        }

        if (root.right != null && root.right.val - 1 == root.val) {
            rightDown = right.down;
        }

        up = Math.max(leftUp, rightUp) + 1;
        down = Math.max(leftDown, rightDown) + 1;

        longest = Math.max(longest, up + down - 1);

        return new Result(up, down);
    }

    class Result {
        int up;
        int down;

        public Result(int up, int down) {
            this.up = up;
            this.down = down;
        }
    }