比较left与left、right与right的递归将不起作用，因为可以使用相同的键，但拓扑结构不同。您需要按顺序访问两棵树中并行的节点。
在不使用递归或额外内存的情况下遍历树的一种方法是通过morris遍历，在morris遍历中，您临时将树放在其左子树的最右边位置，然后通过跟随右指针从递归中“返回”。
这是一个c语言的实现，因为我有一个。在java中不会有那么大的不同。这个 rightmost_to() 函数返回当前节点左边子节点中最右边的节点，或当前节点本身。您使用它将当前节点放在正确的子节点中，因此当您到达该点时，向右模拟从递归返回。

void morris(stree *t)
{
  struct node *curr = *t;
  while (curr) {
    if (!curr->left) {
      printf("%d\n", curr->value);
      curr = curr->right;
    } else {
      stree pred = *rightmost_to(&curr->left, curr);
      assert(pred->right == 0 || pred->right == curr);
      if (pred->right == 0) {
        pred->right = curr;
        curr = curr->left;
      } else {
        printf("%d\n", curr->value);
        pred->right = 0;
        curr = curr->right;
      }
    }
  }
}

您将按顺序访问每个节点，无需递归，也无需使用额外的内存。无论何时递归，都会将所处的节点放在最右边的位置，因此会自动返回到它。您可以意识到您是第二次看到节点，因为您在搜索最右边的节点时找到了它。然后你恢复树而不是再次向左。
如果你需要比较两棵树，有两个当前节点，你应该很好。它确实使用了一个额外的函数， rightmost_to() ，但它是一个简单的循环，您可以轻松地嵌入而不产生任何问题。如果你那样做的话，那是一两行。
如果允许您在节点中放置父指针，我认为您也可以遍历树，而无需使用额外内存执行以下操作：

# define left_child(t) \

  ((t)->parent && (t)->parent->left == (t))
void parent_traverse(stree t)
{
  enum { DOWN, UP } state = DOWN;
  while (t) {
    switch (state) {
      case DOWN:
        // Recurse as far left as we can...
        while (t->left) { t = t->left; }
        // Emit the leaf we find there
        printf("(,%d,", t->value); // VISIT
        // Then go right, if we can, or up if we can't.
        if (t->right) { t = t->right; }
        else          { state = UP; }
        break;

      case UP:
        if (!t->parent) return; // we have returned to the root...
        if (left_child(t)) {
          // Returning from a left child, we emit the parent
          t = t->parent;
          printf(",%d,", t->value); // VISIT
          // Then we go right if we can't, or continue up
          // (t is already the parent) if we cannot.
          if (t->right) { t = t->right; state = DOWN; }
        } else {
          // Returning from a right child just means going up
          t = t->parent;
        }
        break;
    }
  }
}

对不起，又是c了，不过看看怎么回事 t 当我们在树中运行时，会更新到它的左、右或父节点。我从我的一些代码中删掉了它，我可能把它复制错了，但你应该明白。你可以跟踪你移动的方向，基本上沿着树的“边缘”移动，从左到下，从下到上，再从下到右，再从下到上，等等。如果两棵树都有状态，那么应该能够在这两棵树中并行地进行遍历。每当代码“访问”一个节点时，您都会比较这两个节点。
我不知道这有多有用，但至少有两种方法可以比较两棵树，它们只有恒定的额外内存使用，没有递归。
当然，如果它是一个简单的赋值，并且时间复杂度无关紧要，那么可以遍历一棵树，然后在o（n logn）（平衡）或o（n^2）中查找另一棵树