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

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

思路一(traversal + divide conquer)

1. 自底向上组成lcs, 用一个全局变量去记录哪个是最大的
2. 根节点lcs 起始为1, 然后和左节点lcs + 1, 以及右节点lcs + 1 作对比
3. 取最大, 更新全局变量, 并返回根节点lcs

    public int longestConsecutive(TreeNode root) {
        max = Integer.MIN_VALUE;
        helper(root);
        return max;
    }

    private int max;

    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

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

        int rootLCS = 1;
        if (root.left != null && root.left.val - root.val == 1) {
            rootLCS = Math.max(rootLCS, left + 1);
        }
        if (root.right != null && root.right.val - root.val == 1) {
            rootLCS = Math.max(rootLCS, right + 1);
        }
        max = Math.max(max, rootLCS);

        return rootLCS;
    }

思路二(divide conquer)

1. 将最大值放在返回里面向上传递比较

    private class ResultType {
        int maxInSubtree;
        int maxFromRoot;
        public ResultType(int maxInSubtree, int maxFromRoot) {
            this.maxInSubtree = maxInSubtree;
            this.maxFromRoot = maxFromRoot;
        }
    }

    public int longestConsecutive(TreeNode root) {
        return helper(root).maxInSubtree;
    }

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

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

        // 1 is the root itself.
        ResultType result = new ResultType(0, 1);

        if (root.left != null && root.val + 1 == root.left.val) {
            result.maxFromRoot = Math.max(
                result.maxFromRoot,
                left.maxFromRoot + 1
            );
        }

        if (root.right != null && root.val + 1 == root.right.val) {
            result.maxFromRoot = Math.max(
                result.maxFromRoot,
                right.maxFromRoot + 1
            );
        }

        result.maxInSubtree = Math.max(
            result.maxFromRoot,
            Math.max(left.maxInSubtree, right.maxInSubtree)
        );

        return result;
    }

思路三(Traverse + Divide Conquer)

1. traverse (函数输入参数) 用于当前点的lcs,
2. divide conquer返回的是全局最大的lcs

    public int longestConsecutive(TreeNode root) {
        return helper(root, null, 0);
    }

    private int helper(TreeNode root, TreeNode parent, int lengthWithoutRoot) {
        if (root == null) {
            return 0;
        }

        int length = (parent != null && parent.val + 1 == root.val)
            ? lengthWithoutRoot + 1
            : 1;
        int left = helper(root.left, root, length);
        int right = helper(root.right, root, length);
        return Math.max(length, Math.max(left, right));
    }