Help with DFS approach


  • 0
    S

    What is wrong with my code? this test-case [1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5] is failing, and because I don't know the true structure from the array I'm having a hard time debugging. My approach is a DFS solution where I remember the min level while traversing.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            
            if(root == null){
                return true;
            }
            
            int min = 999;
            int current = 1;
            
            HashSet<TreeNode> currentLevel = new HashSet<TreeNode>();
            currentLevel.add(root);
            
            //Keep looping while we have levels
            while(!currentLevel.isEmpty()){
             
               HashSet<TreeNode> nextLevel = new HashSet<TreeNode>();
               Iterator iterator = currentLevel.iterator(); 
               
               
               //add all children to next level
               //check for null to set min
               while(iterator.hasNext()){
                   TreeNode currentNode = (TreeNode) iterator.next();
                   if(currentNode.right != null){
                       nextLevel.add(currentNode.right);
                   }else if(min == 999){
                       min = current;
                   }
                   
                   if(currentNode.left != null){
                       nextLevel.add(currentNode.left);
                   }else if(min == 999){;
                       min = current;
                   }
               }
               
                
                //Finished filling next level
                //increment and check
                if(current - min > 1){
                   return false;
               }
               current++;
               currentLevel = nextLevel;
            }
            return true;
        }
    }
    

Log in to reply
 

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