algorithm - 使用树旋转将一棵二叉树转换为另一棵二叉树

Question

给定两个随机二叉树。我需要找到一个旋转序列，以便在我完成旋转后第一棵树等于第二棵树。

例如:

• 树 1 的根节点为 0，左节点为 1，右节点节点为 2
• 二号树以1为根，右 child 为0，zeros右 child 为2
• 输出:围绕节点 0 向右旋转。

如何为随机二叉树执行此操作？

Answer 1

对于随机二叉树，这是不可能的。

例如，考虑这两棵树:树 1 的根是 0，0 的右 child 是 1；树 2 的根是 1，树 1 的右 child 是 0。很明显，我们不能通过旋转将树 1 变为树 2。

但是可以对随机二叉搜索树执行此操作(因为较大的元素将位于较小元素的右侧)。我们可以在树 1 中找到树 2 的根，并将其旋转到根。然后我们就进入它的左右子树递归求解。

编辑

如果保证答案始终存在，那么我们可以将它们视为二叉搜索树(因为旋转将保持二叉搜索树的属性)。实际上，我们可以重新标记两棵树的节点，将它们变成二叉搜索树，但这不是解决这个问题所必须的。

现在我们可以使用以下算法递归地将 Tree #1 更改为 Tree #2。

procedure solve(tree1: the first tree, tree2: the second tree)
    return if either tree1 or tree2 is empty
    r := root of tree2
    find r in tree1 and rotate r to the root
    solve(left subtree of the root of tree1, left subtree of the root of tree2)
    solve(right subtree of the root of tree1, right subtree of the root of tree2)