1 5
/ \ |
2 3 --> 2
/ \ / \ / \
4 5 6 7 1 4
|
3
/ \
6 7
假设您有一棵像左边的二叉树,并尝试将其转换为右边的二叉树。
它所做的是碰撞二叉树的“任何”单个叶节点——在本例中为“5”——这使叶节点成为新的根节点。原始根节点(及其子节点)——本例中的“1”及其子节点——占据了当时的叶节点空间。
一般的算法是什么?
谢谢你的帮助。
最佳答案
这在很大程度上取决于支持二叉树的结构(例如,是否存储每个节点的父节点,等等)。假设你存储了节点的值和左右后代(最基本的信息),问题就简化为“反转”从当前根向下到将成为新根的节点的所有弧。我猜是这样的,在 Java 风格的伪代码中:
void rev(Node u, Node v) {
// make v point back to u
if (v.left == null) v.left = u;
else v.right = u;
// free edge from u to link up
if (u.left == v) u.left = null;
else u.right = null;
}
boolean reroot(Node root, Node parent, Node newRoot) { // assumes that newRoot is a leaf
if (root != null)
if (root == newRoot) {
rev(root, parent);
return true;
} else {
if (reroot(root.left, root) || reroot(root.right, root)) {
rev(root, parent);
return true;
}
}
}
return false;
}
不过,我没有测试上面的代码。
编辑:初始调用将是 reroot(currentRoot, null, newRoot);
关于algorithm - 二叉树变换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26855893/