arrays - 检查两个二叉搜索树是否具有相同的中序遍历

Question

检查两个二叉搜索树是否具有相同的中序遍历。我天真的方法是按顺序遍历给定的两棵树并将每个元素分别复制到一个数组中，然后检查这两个数组是否相同。但我觉得我们应该能够将元素从一棵树复制到一个数组中，然后使用该数组动态验证另一棵树，而不是使用两个数组。或者更好的是，可能有一种方法可以在不使用任何数组的情况下做到这一点。我的代码如下，不确定我的 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));
} 

Answer 1

我们可以用更好的空间复杂度 O(1)我们可以使用 Morris Traversal 遍历树并逐个元素地比较值。

对于以下实现，我假设两棵树都具有相同数量的节点。

  bool isSame(root1, root2){
    while(root1!=null && root2!=null){
        while(root1->left!=NULL){
            auto maxleft = getmaxnode(root1->left);
            maxleft->right = root1;
            auto next = root1->left;
            root1->left = NULL;
            root1 = next;
        }
        while(root2->left!=NULL){
            auto maxleft = getmaxnode(root2->left);
            maxleft->right = root2;
            auto next = root2->left;
            root2->left = NULL;
            root2 = next;
        }
        if(root1->val != root2->val) return false;
    }
    return true;
}