我遇到了一些问题,问题如下:
给定一个预先构造的二叉搜索树和一个数组,确定该数组是否会生成相同的二叉搜索树。
现在,这个问题将为您预先构造一个 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 中的位置,如果父级已被访问过,则返回假的?
最佳答案
一种方法是从数组构建一个新的 BST,然后比较两棵树。想一想如何一次构建一个节点的树。
现在,每个节点都有一个 visited
标志,我们从所有标志都为 false 开始,那么逻辑是:
对于数组中的每个值,在树中查找该值的节点(目标节点):
如果没有找到目标节点,则答案是否定的(树和数组具有不同的值)。
如果到目标节点的路径踩到了任何尚未访问过的节点,则答案为“否”(顺序错误)。
(可选)如果目标节点已被访问,则抛出
IllegalArgumentException
(数组中不允许出现重复值)。标记访问过的目标节点。
扫描树(BFS 或 DFS,无所谓),如果发现任何未访问的节点,则答案是否定的(树和数组具有不同的值)。
如果您到达这里,答案是肯定的。
关于java - 确定数组是否会生成与提供的相同的 BST - 使用递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58496604/