[Time Limit Exceeded] my solution using level order traversal


  • 0
    L

    my submit result is Time Limit Exceeded;
    I try to solve it by checking every level's symmetric. And in every level's check, i use an array to store the previous level's node; traversal the previous level to get the current level's nodes ; then check the current level's nodes' symmetric; ... until the current level is all "#".
    And i thought my solution's time complexity is linear... where is the wrong?
    below is my code; thanks!

      public boolean isSymmetric(TreeNode root) {
        /**
         * level traversal the tree and test its symmetric each level 
         * */
        if( root == null ) return true;
        ArrayList<TreeNode>  preList     = new ArrayList<TreeNode>();
        ArrayList<TreeNode>  currList    = new ArrayList<TreeNode>();
        preList.add(root);
        for(int i=0; ; i++){  // travesal the ith level
          boolean overFlag = true;
          for(int j=0; j<Math.pow(2,i); j++){
              TreeNode temp = preList.get(j);
              if(temp==null){
                  currList.add(null);
                  currList.add(null);
              }else{
                  overFlag = false;  // the next level is not empty
                  currList.add(temp.left);
                  currList.add(temp.right);
              }
          }
          if(overFlag) return true;  // the next level's node are all empty
          if(checkArraySymmetric(currList)) preList = currList;
          else return false;
          currList = new ArrayList<TreeNode>();
        }
    }
    
    
     // check the list's symmetric 
     private boolean checkArraySymmetric(ArrayList<TreeNode> list){
        for(int i=0; i<list.size()/2; i++){
            TreeNode head = list.get(i);
            TreeNode tail = list.get(list.size()-i-1);
            if( head == null && tail == null ) continue;
    	    if( (head == null && tail != null) || (head != null && tail == null) ) return false;
    	    if( head.val != tail.val ) return false;
        }
        return true;
    }

Log in to reply
 

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