java - BST 的共同元素

Question

我正在使用 BST，我被要求获取 2 个 BST 中的公共(public)元素并将它们插入到第三个 BST 中。我的方法应该返回第三个 BST。我在使用 LL 时也做过同样的事情，但现在对于 BST，我不知道从哪里开始!我已经想出了一个解决方案，但问题是它与树的根部一起工作，这对我来说似乎并不正确。我很迷茫，找不到起点。非常感谢您的建议。

编辑:我已经在 BST 类中创建了该方法

 public BinarySearchTree common(BinarySearchTree t1,BinarySearchTree t2){
    return commonValues(t1.root,t2.root);
}


private BinarySearchTree commonValues(BinaryTreeNode node1, BinaryTreeNode node2) {
    //  BinaryTreeNode temp1;
    //  BinaryTreeNode temp2;
    BinarySearchTree tree = new BinarySearchTree();

    if (node1 == null && node2 == null) {
        System.out.println("Empty trees!");
    } else {
        if (node1.getInfo().equals(node2.getInfo())) {
            tree.insert(node1.getInfo());
        } else if (node1.getInfo().compareTo(node2.getInfo()) > 0) { // go left
            node1 = node1.getLlink();
            commonValues(node1, node2);
        } else {
            node2 = node2.getRlink();
            commonValues(node1, node2);
              }
       }
       return tree;
   }

每次运行时我都会遇到 NullPointerException

Answer 1

你的循环控制变量似乎什么也没做。基本上看起来就像根据两棵树的大小执行相同的语句。

不确定 BinarySearchTree 实现，但我认为这是可行的:

我们想要使用公共(public)元素创建一个新的 BST。查找共同元素:

1. 新树 (T3) 将仅与 (T1, T2) 中较小的树一样大
2. 比较 T1 和 T2 的大小
3. 使用较小的树来搜索较大的树。遍历于预购方式。对于每个节点，如果 search 返回 true，则创建一个插入T3