java - 确定数组是否会生成与提供的相同的 BST - 使用递归

Question

我遇到了一些问题，问题如下:

给定一个预先构造的二叉搜索树和一个数组，确定该数组是否会生成相同的二叉搜索树。

现在，这个问题将为您预先构造一个 BST，然后它将通过以下代码运行:

boolean valid = true;
for (int i = 0;valid && i < arr.length; i ++) {
   valid &= tree.checkPattern(arr[i]);
}

//These two methods below are in a different class. For every element in the array,
//the checkPattern method will be called, initially passing in the root of the BST
public void checkPattern(int key) {
   recursiveFunction(root, key);
}

public boolean recursiveFunction(TreeNode current, int key){
 // Recursive function 
}

目标是编写recursiveFunction(root, arr[i])，提示是 TreeNode 类包含您要使用的visited boolean 值帮助这个算法。

我似乎不太清楚如何解决这个问题...给定一个 key ，您是否应该检查它在主要 BST 中的位置，如果父级已被访问过，则返回假的？

Answer 1

一种方法是从数组构建一个新的 BST，然后比较两棵树。想一想如何一次构建一个节点的树。

现在，每个节点都有一个 visited 标志，我们从所有标志都为 false 开始，那么逻辑是:

• 对于数组中的每个值，在树中查找该值的节点(目标节点):

  • 如果没有找到目标节点，则答案是否定的(树和数组具有不同的值)。

  • 如果到目标节点的路径踩到了任何尚未访问过的节点，则答案为“否”(顺序错误)。

  • (可选)如果目标节点已被访问，则抛出 IllegalArgumentException(数组中不允许出现重复值)。

  • 标记访问过的目标节点。

• 扫描树(BFS 或 DFS，无所谓)，如果发现任何未访问的节点，则答案是否定的(树和数组具有不同的值)。

• 如果您到达这里，答案是肯定的。