检查两棵二叉搜索树是否具有相同的中序遍历。我的朴素方法是分别对给定的两棵树进行中序遍历并将每个元素复制到不同的数组中,然后检查这两个数组是否相同。但我觉得我们应该能够只从一棵树上复制元素到一个数组中,并使用该数组即可在运行时验证另一棵树,而无需使用两个数组。或者更好的方法是,可能有一种方法可以在不使用任何数组的情况下完成。我的代码如下,不确定hasSameInOrder()的实现是否正确。还是说我们可以完全不使用数组来做呢?请注意,两棵树具有相同的中序遍历意味着如果在中序遍历时将元素复制到数组中,则两个结果数组应具有相同的值。因此,它们不一定具有相同的结构才能具有相同的中序遍历。
public boolean checkTwoBSTHaveSameInOrder(Node n1, Node n2) {
LinkedList<Node> queue = new LinkedList<Node>();
inOrder(n1, buffer);
hasSameInOrder(n2, queue)
return queue==null? false: true;
}
public void inOrder(Node node, LinkedList<Node> queue) {
if (node==null)
return;
inOrder(node.left, queue);
queue.add(node);
inOrder(node.right, queue);
}
public void hasSameInOrder(Node node, LinkedList<Node> queue) {
if (node==null)
return;
hasSameInOrder(n2.left, queue));
if (queue==null)
return;
else {
if (node!=queue.poll())
queue=null;
}
hasSameInOrder(n2.right, queue));
}