Easy Java DFS, is there better time complexity solution?


  • 65
    C

    Just very intuitive depth-first search, send cur node value to the next level and compare it with the next level node.

    public class Solution {
        private int max = 0;
        public int longestConsecutive(TreeNode root) {
            if(root == null) return 0;
            helper(root, 0, root.val);
            return max;
        }
        
        public void helper(TreeNode root, int cur, int target){
            if(root == null) return;
            if(root.val == target) cur++;
            else cur = 1;
            max = Math.max(cur, max);
            helper(root.left, cur, root.val + 1);
            helper(root.right, cur, root.val + 1);
        }
    }

  • 0
    C

    I think it would be O(n) anyway ..


  • 0
    G

    Any way we can avoid using static?


  • 5
    F

    Nice solution, by using target, can make it more general.
    Using object like a 1 element int array to save temporary state param:

      public int longestConsecutive(TreeNode root) {
        int[] lens = new int[1];
        if (root == null)  return 0;
        helper(root, 0, lens, root.val);
        return lens[0];
      }
    
      private void helper(TreeNode root, int cur, int[] cnt, int target) {
        if (root == null)  return;
        if (root.val == target)  cur++;
        else  cur = 1;
        cnt[0] = Math.max(cur,cnt[0]);
        helper(root.left, cur, cnt, root.val+1);
        helper(root.right, cur, cnt, root.val+1);
      }

  • 0

    @fxrcode Why bother using an array? I think using a instance variable is perfectly enough. Or is there anything bad about using a instance variable?


  • 5
    D

    Nice use of target. I removed the instance variable.

    public int longestConsecutive(TreeNode root) {
    	if (root == null) {
    		return 0;
    	}
        return DFS(root, root.val + 1, 1, 1);
    }
    
    private int DFS(TreeNode node, int target, int curr, int max) {
    	if (node == null) {
    		return max;
    	}
    	if (node.val == target) {
    		curr++;
    		max = Math.max(max, curr);
    	} else {
    		curr = 1;
    	}
    	return Math.max(DFS(node.left, node.val + 1, curr, max), DFS(node.right, node.val + 1, curr, max));
    }

  • 0
    Y

    nice solution!


  • 5

    Share my Java code:

    public int longestConsecutive(TreeNode root) {
         
         if(root == null) return 0;
         return Math.max(helper(root.left,root.val + 1, 1),helper(root.right,root.val + 1,1));
    }
    
    private int helper(TreeNode n, int t, int c){
        if(n == null) return c;
        if(n.val != t) c = 1;
        else c++;
        
        int m =  Math.max(helper(n.left,n.val + 1, c),helper(n.right,n.val + 1,c));
        return Math.max(m,c);
    }

  • 0
    P

    My another approach is to take max of the length till now and the max of left and right length. Following is the simple implementation :

    public int longestConsecutive(TreeNode root) {
            if(root == null)
                return 0;
            return longestConsecutive(root, null, 0);
        }
        public int longestConsecutive(TreeNode root, TreeNode prev, int len) {
            if(root == null)
                return len; // reached the leaf node.
    
            int leftLen = 0, rightLen = 0;
            if(prev != null && root.val == prev.val + 1) { // Increasing node found
                leftLen = longestConsecutive(root.left, root, len + 1);
                rightLen = longestConsecutive(root.right, root, len + 1);
            }
            else { // This node breaks the increasing property. So start again from here.
                leftLen = Math.max(len, longestConsecutive(root.left, root, 1));
                rightLen = Math.max(len, longestConsecutive(root.right, root, 1));
            }
    
                
            return Math.max(leftLen, rightLen);
            
        }
    

  • 0

    @piyush121 Same idea! Would this one make sense?

        public int longestConsecutive(TreeNode root) {
            if (root == null) return 0;
            return dfs(root, 1);
        }
    
        private int dfs(TreeNode root, int len) {
            int left = 0, right = 0;
            if (root.left != null)
                left = dfs(root.left, root.val + 1 == root.left.val ? len + 1 : 1);
            if (root.right != null)
                right = dfs(root.right, root.val + 1 == root.right.val ? len + 1 : 1);
            return Math.max(len, Math.max(left, right));
        }
    

  • 0

    share my java solution

    public class Solution {
        public int longestConsecutive(TreeNode root) {
            if(root == null) return 0;
            int[] max = new int[]{1};
            helper(root, max);
            return max[0];
        }
        
        private int helper(TreeNode root, int[] max){
            if(root.left == null && root.right == null) return 1;
            int cur = 1;
    
            if(root.left != null){
                int left = helper(root.left, max) +1;
                //if we can update the current value on current layer
                if(root.val + 1 == root.left.val){
                    cur = Math.max(cur, left);
                }
            }
    
            if(root.right != null){
                int right = helper(root.right, max) +1;
                if(root.val + 1 == root.right.val){
                    cur = Math.max(cur, right);
                }
            }
    
            max[0] = Math.max(cur, max[0]);
            return cur;
        }
    }
    

  • 0
    C

    I think it will be more concise and easier to read if we do not pass max around and use a global variable.

    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        return dfs(root, 0, root.val);
    }
    
    public int dfs(TreeNode root, int seq, int target){
        if (root == null) return seq;
        if (root.val == target) seq++; 
        else seq =1;
        int left = dfs(root.left, seq, root.val+1);
        int right = dfs(root.right, seq, root.val+1);
        return Math.max(seq,Math.max(left,right));
    }
    

    '''


  • 0
    J

    That's it. You killed it. Great solution man!


  • 0
    F

    Same idea

    public class Solution {
        int max = 0;
        public int longestConsecutive(TreeNode root) {
            if(root == null) return 0;
            helper(root,1);
            return max;
        }
        public int helper(TreeNode root, int count){
            max = Math.max(max,count);
            int left = 0,right = 0;
            if(root.left != null)
                left = helper(root.left,(root.left.val - root.val == 1)?count+1:1);
            if(root.right != null)
                right = helper(root.right,root.right.val - root.val == 1?count+1:1);
            return Math.max(left,right);
        }
    }
    

    But after looking yours, I found mine is more stupid... No need to return value in the sub method. Only update the max length within recursive.

    Updated:

    public class Solution {
        int max = 0;
        public int longestConsecutive(TreeNode root) {
            if(root == null) return 0;
            helper(root,1);
            return max;
        }
        public void helper(TreeNode root, int count){
            max = Math.max(max,count);
            if(root.left != null)
                helper(root.left,(root.left.val - root.val == 1)?count+1:1);
            if(root.right != null)
                helper(root.right,root.right.val - root.val == 1?count+1:1);
        }
    }
    

  • 0
    T
    This post is deleted!

Log in to reply
 

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