数据结构。返回相同形状的BST与另一个BST的值。

Question

嘿，我有一个问题，我需要描述一个算法，得到2个二进制搜索树，T1和T2。这两棵树的每个节点都有不同的值，该算法应该返回一个形状与T2相同的二进制搜索树，但其值为T1，时间复杂度为 O(n) 哪儿 n 是元素的数量（两棵树都是一样的

同等拓扑学

例如

T1(定义值)

T2（定义形状）。

应该返回：

我目前尝试的是考虑中值的平均数 但是每次都没有用，或者考虑建立一棵AVL树，然后旋转它，直到我们找到解决方案，但是我没有想到这是否会成功，或者是时间上的复杂性 O(n). 任何帮助将被感激! 谢谢你！我有一个问题，我需要描述一个算法，得到2个二进制搜索树，T1和T2。

Answer 1

遍历T1，并将值写入一个数组（按排序顺序）。然后创建T2的副本（如果需要的话）并遍历它，从数组中逐一写入值。这将使用2次遍历，所以是Θ(n)。按照左子树-顶点-右子树的顺序遍历两棵树。