在两个BST中寻找公共节点的最佳方法是什么? [英] What is the optimal way to find common nodes in two BST
本文介绍了在两个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屋!
查看全文