O(n) java solution with recursion


  • 0
    S
    class Solution {
        int ans = 0;
        
        public int longestConsecutive(TreeNode root) {
            traverse(root);
            return ans;
        }
        
        // first is count of increasing, second is decreasing
        public int[] traverse(TreeNode node) {
            if (node == null) {
                return new int[] {0,0};
            }
            int[] leftCount = traverse(node.left);
            int[] rightCount = traverse(node.right);
            int[] count = new int[] {1,1};
            
            if (node.left != null) {
                if (node.val == node.left.val + 1) {
                    count[0] = leftCount[0] + 1;
                } else if (node.val == node.left.val - 1) {
                    count[1] = leftCount[1] + 1;
                }
            }
            
            if (node.right != null) {
                if (node.val == node.right.val + 1) {
                    count[0] = Math.max(rightCount[0] + 1, count[0]);
                } else if (node.val == node.right.val - 1) {
                    count[1] = Math.max(rightCount[1] + 1, count[1]);
                }
            }
            
            ans = Math.max(ans, count[0] + count[1] - 1);
            return count;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.