java - 顺序遍历错误？

Question

这个递归顺序遍历方法有一些问题 我的代码应该按顺序遍历给定的树，如果正确则返回 true。我通过遍历它并将元素添加到 arrayList 来做到这一点。我有一个 isSorted 方法，如果数组列表已排序(每次添加数组列表元素时都会完成)，它返回 1，否则返回 0。

它的工作是返回对应于它是否已排序的正确性 1 或 0，但之后它不会停止执行。因为如果它没有排序，那么可以安全地说顺序遍历没有正确完成，但它说是。谁能帮忙？

 public ArrayList<Integer> inOrderCheck = new ArrayList<Integer>();


boolean checkBST(Node root) {

   if(root != null){
       checkBST(root.left);
       if(addToList(root.data) == 0){
           return false;
       }

       checkBST(root.right);

   }


    return true;

   // Integer[] inOrderArray = inOrderCheck.toArray(new Integer[inOrderCheck.size()]);




}

int addToList(int data){

    //System.out.println("Initial size of inOrderCheck: " + inOrderCheck.size());
if(!(inOrderCheck.contains(data))){
   // System.out.println("Adding: " + data);
      inOrderCheck.add(data);
}

//System.out.println(" size of inOrderCheck after adddition: " + inOrderCheck.size());
   // System.out.println("Contents of inOrderCheck: " + inOrderCheck);   

  //  System.out.println("Result of isSorted: " + isSorted());   

return isSorted();    
}



int isSorted(){

int sorted = 0;        
for (int i = 1; i < inOrderCheck.size(); i++) {
     //System.out.println("Result of isSorted: " + inOrderCheck.get(i-1) + " "+ inOrderCheck.get(i));   
    if (inOrderCheck.get(i-1) < (inOrderCheck.get(i)) ) {
        sorted = 1;
    }else
        sorted = 0;
}

return sorted;
}

Answer 1

您忽略了递归调用返回的值。如果对左子树或右子树的任一调用返回 false，则您应该返回 false。

boolean checkBST(Node root) {
    if (root != null) {
        if (!checkBST(root.left))
            return false;
        if (!addToList(root.data))
            return false;
        if (!checkBST(root.right))
            return false;
    }   
    return true;
}

此外，您的 isSorted 方法有一些问题。 首先，它应该返回 boolean 值。其次，当列表只包含一个元素时，它不应返回 0。

我会把它改成:

boolean isSorted() {     
    for (int i = 1; i < inOrderCheck.size(); i++) { 
        if (inOrderCheck.get(i-1) >= inOrderCheck.get(i)) {
            return false;
        }
    }
    return true;
}

boolean addToList(int data) {
    if(!inOrderCheck.contains(data)) {
        inOrderCheck.add(data);
    } else {
        return false;
    }
    return isSorted();
}