arrays - 列出出现在两个列表中的元素？

Question

给定两个排序数组(当然没有重复)，有没有办法找出并打印出现在两个数组中的所有元素？

我知道是否可以通过迭代一个数组并构建一个哈希表，然后迭代另一个数组并查找构建的表来获得。但这需要 O(n) 的空间。

我正在尝试看看是否有这样一种方法需要不断增加额外空间，并且只需要对每个数组进行不超过一次的迭代。可能吗？

现在如果上述问题是可能的，如果两个排序列表存储在两个二叉搜索树中，那么在给定共谋限制的情况下，相同的方法是否仍然适用？

Answer 1

对于数组，执行与合并操作等效的操作，但没有输出。在合并过程中，将检测到任何重复项。这将只涉及每个列表的一次传递，并且将在到达任一列表的末尾时立即终止。

一棵二叉搜索树可以使用栈来迭代遍历，但最坏情况下的栈空间是O(n)。莫里斯遍历(进行网络搜索)可以在不使用堆栈的情况下遍历二叉树，并且通过更改和恢复树中的链接以 O(n) 的时间复杂度(大多数节点将被访问多次，但时间开销是倍数) n 的时间复杂度仍为 O(n))。典型的 Morris 遍历函数在整棵树上运行。这将需要更改，以便它按顺序返回每个节点，以便可以使用类似合并的逻辑来检查重复项。我为此编写了一些测试代码，以便在您遇到困难时提供帮助。

当按顺序遍历二叉树时，每个当前节点都有一个前驱节点，即按顺序出现在当前节点之前的节点。前驱节点将有一个空的“右”指针。在 Morris 遍历期间，每个前驱节点的“右”指针从 null 更改为指向它的后继节点。最终到达一个前驱节点时，跟随它的右指针到达它的后继节点，然后后继节点的前驱节点的右指针恢复为空。

已经 2 天了，下面是 Morris 遍历函数的示例代码，该函数返回一个指向每个节点的指针。部分逻辑在 main() 的 for 循环中，它在再次调用遍历函数之前将返回的指针向右推进(另一种方法是有一个向右推进的辅助函数，然后调用主遍历函数) :

#include<stdio.h>
#include<stdlib.h>

/* binary tree node */
typedef struct BTNODE_
{
    struct BTNODE_* left;
    struct BTNODE_* right;
    int data;
}BTNODE;

/* traverse binary tree without stack */
/* initial input parameter is pointer to root */
/* predecessor of cur is largest value < cur */
/* predecessor of cur = cur->left->right->right->right ... */
BTNODE * MorrisTraversal(BTNODE *cur)
{
BTNODE *pre;
    if(cur == NULL)
        return(NULL);
    while(cur != NULL){
        /* if left end of branch, return */
        if(cur->left == NULL)
            return(cur);
        /* advance pre to predecessor of cur */
        pre = cur->left;
        while(pre->right != NULL && pre->right != cur)
            pre = pre->right;
        /* if right end of branch, change pre->right = cur */
        /*  and advance cur left */
        if(pre->right == NULL){
            pre->right = cur;
            cur = cur->left;
        /* else back at cur, so restore pre->right = NULL */
        /*  and return */
        } else {
            pre->right = NULL;
            return(cur);
        }
    }
    return(NULL);
}

BTNODE* newbtNode(int data)
{
BTNODE* btNode = (BTNODE*) malloc(sizeof(BTNODE));
    btNode->left = NULL;
    btNode->right = NULL;
    btNode->data = data;
    return(btNode);
}

int main()
{
BTNODE *cur;
/* create a 15 element binary tree */
BTNODE *root = newbtNode(8);
    root->left                = newbtNode( 4);
    root->left->left          = newbtNode( 2);
    root->left->left->left    = newbtNode( 1);
    root->left->left->right   = newbtNode( 3);
    root->left->right         = newbtNode( 6);
    root->left->right->left   = newbtNode( 5);
    root->left->right->right  = newbtNode( 7);
    root->right               = newbtNode(12);
    root->right->left         = newbtNode(10);
    root->right->left->left   = newbtNode( 9);
    root->right->left->right  = newbtNode(11);
    root->right->right        = newbtNode(14);
    root->right->right->left  = newbtNode(13);
    root->right->right->right = newbtNode(15);
    for(cur = root; cur; cur = cur->right){
        cur = MorrisTraversal(cur);
        printf("%2d ", cur->data);
    }
    return 0;
}