DFS Solution with O(n) runtime


  • 0
    L
    public class Solution {
        class Node {
            int increasingLongest;
            int decreasingLongest;
            
            Node(int increasing, int decreasing) {
                increasingLongest = increasing;
                decreasingLongest = decreasing;
            }
        }
        
        
        public int longestConsecutive(TreeNode root) {
            int[] maxLength = new int[]{0};
            helper(root, maxLength);
            return maxLength[0];
        }
        
        private Node helper(TreeNode root, int[] maxLength) {
            if (root == null) {
                return new Node(0, 0);
            }
            
            Node leftNode = helper(root.left, maxLength);
            Node rightNode = helper(root.right, maxLength);
            
            int increasing = 1;
            int decreasing = 1;
            
            if (root.left != null) {
                if (root.val == root.left.val + 1) {
                    increasing = leftNode.increasingLongest + 1;
                }
                if (root.val == root.left.val - 1) {
                    decreasing = leftNode.decreasingLongest + 1;
                }
            }
            
            if (root.right != null) {
                if (root.val == root.right.val + 1) {
                    increasing = Math.max(increasing, rightNode.increasingLongest + 1);
                }
                if (root.val == root.right.val - 1) {
                    decreasing = Math.max(decreasing, rightNode.decreasingLongest + 1);
                }
            }
            
            maxLength[0] = Math.max(maxLength[0], increasing + decreasing - 1);
            
            return new Node(increasing, decreasing);
        }
    }
    

Log in to reply
 

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