如何用二叉树t1的值和二叉树t2的形状构建二叉树

Question

我正在尝试解决一个问题，但确实无法解决。

问题：描述一种算法，该算法接受两个二叉搜索树-T1，T2，然后将具有拓扑（形状）的T2树的值的二叉搜索树返回到T1。该算法必须在时间O（n）上运行。

谢谢！

Answer 1

如果您知道如何对二叉树中的节点执行有序遍历，那么您已经接近解决方案。

在两棵树中并行执行这样的遍历。因此，当您访问T1的第一个节点（按顺序遍历）时，还要访问T2的第一个节点。然后将值从T2节点复制到T1节点。继续进行下一个节点对（在T1和T2中，根据它们的顺序遍历），然后重复。