Java O(n) accepted dfs solution without global variable


  • 0
    M
        public int longestConsecutive(TreeNode root) {
            Pair p = longest(root);
            return p.max;
        }
        
        private Pair longest(TreeNode root) {
            if(root == null) {
                return new Pair(0,0);
            }
            
            if(root.left == null && root.right == null) {
                return new Pair(1,1);
            }
            
            Pair left = longest(root.left);
            Pair right = longest(root.right);
            
            Pair p = new Pair();
            
            if(root.left != null) {
                if(root.val == root.left.val - 1) {
                    p.curr = left.curr + 1;
                } else {
                    p.curr = 1;
                }
            }
            
            if(root.right != null) {
                if(root.val == root.right.val - 1) {
                    p.curr = Math.max(p.curr, right.curr + 1);
                } else {
                    p.curr = Math.max(p.curr, 1);
                }
            }
            
            p.max = Math.max(Math.max(left.max, right.max), p.curr);
            return p;
        }
        
        class Pair {
            int max;
            int curr;
            
            public Pair() {
                this.max = 0;
                this.curr = 0;
            }
    
            public Pair(int curr, int max) {
                this.max = max;
                this.curr = curr;
            }
        }
    

Log in to reply
 

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