549. Binary Tree Longest Consecutive Sequence II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*
Bottom Up DFS Approach

Time Complexity: O(N)
Space Complexity: O(H)

N = Number of nodes in the binary tree.
H = Height of the binary Tree. This will be equal to N if the tree is skewed.
*/
class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] maxLength = new int[1];
        dfsHelper(root, maxLength);
        return maxLength[0];
    }

    private int[] dfsHelper(TreeNode node, int[] maxLength) {
        if (node == null) {
            return new int[] {0,0};
        }
        int inc = 1;
        int dec = 1;
        if (node.left != null) {
            int[] left = dfsHelper(node.left, maxLength);
            if (node.left.val == node.val+1) {
                inc = left[0] + 1;
            } else if (node.left.val == node.val-1) {
                dec = left[1] + 1;
            }
        }
        if (node.right != null) {
            int[] right = dfsHelper(node.right, maxLength);
            if (node.right.val == node.val+1) {
                inc = Math.max(inc, right[0] + 1);
            } else if (node.right.val == node.val-1) {
                dec = Math.max(dec, right[1] + 1);
            }
        }
        maxLength[0] = Math.max(maxLength[0], inc + dec - 1);
        return new int[] {inc, dec};
    }
}