在两个BST中寻找公共节点的最佳方法是什么？ [英] What is the optimal way to find common nodes in two BST

问题描述

我正在寻找在复杂性（空间和时间）方面最优的。

I am looking for the most optimal in terms of complexity(space and time).

到目前为止，我的方法是：
遍历一个树顺序，对于每个nodeId，在第二个树中搜索该nodeId。

My approach until now is: Traverse one tree in-order and for each nodeId, search that nodeId in second tree.

节点结构：

struct node{
    long long nodeId;
    node *left;
    node *right;
};

如有疑问请通知我。

推荐答案

稍微修改的Morris Traversal应该通过类似于合并部分的合并排序来解决解决方案。时间复杂度：O（m + n），空间复杂度：O（1）。

Slightly modified Morris Traversal should solve the solution with movement similar to merge part of merge sort. Time Complexity: O(m + n), Space Complexity: O(1).

这篇关于在两个BST中寻找公共节点的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！