Thinking process I - Traverse + Divide and Conquer

Use a global variable

what's the largest consecutive sequence of left subtree?

what's the largest consecutive sequence of the right subtree?

Does current node can be linked with left or right child?

Mistakes

it's possible that current node can be linked with both left and right child, so, choose the larger one.

public class Solution {
    private int longestNum;
    public int longestConsecutive(TreeNode root) {
        longestNum = 0;
        dfsHelper(root);
        return longestNum;
    }

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

        int result = 1;
        int left = dfsHelper(root.left);
        int right = dfsHelper(root.right);

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

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

        if (longestNum < result) {
            longestNum = result;
        }
        return result;
    }
}

Thinking process II - avoid using global variables

public class Solution {
    public int longestConsecutive(TreeNode root) {
        return root == null ? 0 : Math.max(longestConsecutiveDfsHelper(root.left, 1, root.val),longestConsecutiveDfsHelper(root.right, 1, root.val));
    }

    //check whether current node can be one node in the path from parents, top-down solution
    //return result from the bottom
    private int longestConsecutiveDfsHelper(TreeNode node, int count, int prevValue) {
        if (node == null) return count;

        count = (node.val - prevValue == 1) ? count + 1 : 1;

        int left = longestConsecutiveDfsHelper(node.left, count, node.val);
        int right = longestConsecutiveDfsHelper(node.right, count, node.val);

        return Math.max(count, Math.max(left, right));
    }

}

or

public class Solution {
    public int longestConsecutive(TreeNode root) {
        return dfsHelper(root, null, 0);
    }

    private int dfsHelper(TreeNode node, TreeNode parent, int prevLen) {
        if (node == null) return 0;

        int currLen = (parent == null) ? 1 : (parent.val + 1 == node.val) ? prevLen + 1 : 1;

        int left = dfsHelper(node.left, node, currLen);
        int right = dfsHelper(node.right, node, currLen);

        return Math.max(currLen, Math.max(left, right));
    }
}

Binary Tree Longest Consecutive Sequence II

https://www.lintcode.com/en/problem/binary-tree-longest-consecutive-sequence-ii/

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the length of the longest consecutive sequence path
     */
    class ReturnType {
        int increase;
        int decrease;

        public ReturnType(int i, int d) {
            this.increase = i;
            this.decrease = d;
        }
    }

    private int longestPath = 0;
    public int longestConsecutive2(TreeNode root) {
        dfsHelper(root);

        return longestPath;
    }

    private ReturnType dfsHelper(TreeNode node) {
        if (node == null) return new ReturnType(0, 0);

        ReturnType current = new ReturnType(1, 1);

        ReturnType left = dfsHelper(node.left);
        ReturnType right = dfsHelper(node.right);

        if (node.left != null) {
            if (node.val - node.left.val == 1) {
                current.increase += left.increase;
            } else if (node.left.val - node.val == 1) {
                current.decrease += left.decrease;
            }
        }

        if (node.right != null) {
            if (node.val - node.right.val == 1) {
                current.increase = Math.max(right.increase + 1, current.increase);
            } else if (node.right.val - node.val == 1) {
                current.decrease = Math.max(right.decrease + 1, current.decrease);
            }
        }

        longestPath = Math.max(longestPath, Math.max(current.increase, current.decrease));

        if (node.left != null && node.right != null && (node.val - node.left.val == 1 && node.right.val - node.val == 1)) {
            longestPath = Math.max(longestPath, left.increase + right.decrease + 1);
        }

        if (node.left != null && node.right != null && (node.left.val - node.val == 1 && node.val - node.right.val == 1)) {
            longestPath = Math.max(longestPath, left.decrease + right.increase + 1);
        }

        return current;
    }
}

Binary Tree Longest Consecutive Sequence III

https://www.lintcode.com/en/problem/binary-tree-longest-consecutive-sequence-iii/#

public class Solution {
    /**
     * @param root the root of k-ary tree
     * @return the length of the longest consecutive sequence path
     */
    class ReturnType {
        int up;
        int down;
        int max_len;

        public ReturnType(int u, int d, int len) {
            this.up = u;
            this.down = d;
            this.max_len = len;
        }
    }

    public int longestConsecutive3(MultiTreeNode root) {
        // Write your code here
        return helper(root).max_len;
    }

    private ReturnType helper(MultiTreeNode node) {
        if (node == null) {
            return new ReturnType(0, 0, 0);
        }

        int down = 0, up = 0, max_len = 1;
        for (MultiTreeNode child : node.children) {
            ReturnType rt = helper(child);

            if (child.val - node.val == 1) {
                up = Math.max(up, rt.up + 1);
            } 

            if (node.val - child.val == 1) {
                down = Math.max(down, rt.down + 1);
            } 

            max_len = Math.max(max_len, rt.max_len);
        }

        max_len = Math.max(max_len, down + 1 + up);
        return new ReturnType(up, down, max_len);
    }
}