java - 检查 2 个 BST 的值是否相等

Question

我正在编写一个代码，用于确定 2 个 BST 的值是否相等。

这是我想出的，但它只返回true，我真的不知道问题是什么。

 public boolean same(BSTree t2) {
    return sameTree(root, t2);
  }

    private boolean sameTree(TreeNode n, BSTree other) {//L-M-R
    boolean found = false;
    if (n != null) {
        sameTree(n.getLeftNode(), other);

        if (other.search(n.getData())) {
            found = true;
        }
        sameTree(n.getRightNode(), other);
    }
    return found;
}

在 main 方法中，我创建了 2 个 BST 并在其中插入了值。然后我调用了我习惯用以下方法来调用的方法:

   System.out.println("Are the trees the same: " + tree1.same(tree2));

Answer 1

你的逻辑有问题。这就是它现在正在做的事情:您遍历每个节点。如果在另一个 BST 中找到它，则代码将找到的值设置为 true，但如果它的子级之一不在另一棵树中怎么办？您递归地调用该子函数的函数，结果结果为 false，但对返回值不执行任何操作。最后，您只需检查第一个调用(根)是否在第二个 BST 中。

要解决此问题，请在每次调用后检查返回值是否为 false。如果是，则完全退出递归并返回 false。