Two java recursive solution, top down and bottom up and one Iteration solution using stack


  • 3
    S

    1 divide and conquer bottom up

     public int longestConsecutive(TreeNode root) {	        
    	    if (root == null) {
    	    	return 0 ;
    	    }
    	    helper (root);
    	    return max ;
    	    
    	}
    	int max = Integer.MIN_VALUE ;
    	private int helper (TreeNode root){
    		if (root == null) {
    			return 0 ;
    		}
    		int left = helper (root.left);
    		int right = helper (root.right);
    		int maxLeft = (root.left != null &&  root.left.val - root.val == 1) ? 1 + left : 1;
    		int maxRight = (root.right != null &&  root.right.val - root.val == 1) ? 1 + right : 1;
    		max = Math.max(max, Math.max(maxLeft, maxRight)) ;
    		return Math.max(maxLeft, maxRight) ;
    	}
    

    2 top down

    public int longestConsecutive(TreeNode root) {	    
           if (root == null) return 0 ;
    	   return helper (root,Integer.MAX_VALUE,1); 
    	}
    	
    	private int helper (TreeNode root, int pre, int len){
    		if (root == null ) {
    			return len ;
    		}		
    		if (root.val - pre == 1) {
    			return   Math.max(helper (root.left,root.val,len + 1),  helper (root.right,root.val,len + 1)) ;
    		} else {
    			return Math.max(len,Math.max(helper (root.left,root.val,1),  helper (root.right,root.val,1))) ;
    		}
    	}
    

    3 I use a map and stack to keep track the max path, but a bit memory consuming

    public int longestConsecutive(TreeNode root) {	        
    	    if (root == null) {
    	    	return 0 ;
    	    }
    	    int max = 1 ;
    	    Stack<TreeNode> stack = new Stack<> ();
    	    HashMap<TreeNode,Integer> map = new HashMap<> ();
    	    stack.push(root) ;
    	    map.put(root, 1);
    	    while (!stack.isEmpty()) {
    	      TreeNode cur = stack.pop() ;
    	      int left = cur.left != null && cur.left.val - cur.val == 1 ? map.get(cur) + 1 : 1 ;
    	      int right = cur.right != null && cur.right.val - cur.val == 1 ? map.get(cur) + 1 : 1 ;
    	      max = Math.max(max, Math.max(left, right)) ;
    	      if (cur.right != null) {
    	    	  stack.push(cur.right) ;
    	    	  map.put(cur.right, right) ;
    	      }
    	      if(cur.left != null) {
    	    	  stack.push(cur.left) ;
    	    	  map.put(cur.left, left);	    	  
    	      }	      
    	    }	    
    	    return max ;	    
    	}

Log in to reply
 

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