我在查看面试问题时，最近遇到了一个问题，问如何反转一般的二叉树，就像将其从右侧翻转到左侧。
例如，如果我们有以下二叉树：
6
/ \
3 4
/ \ / \
7 3 8 1
反转它将创建
6
/ \
4 3
/ \ / \
1 8 3 7
你可以看到，新树是原始树的镜像。
我一直想不出如何解决这个问题的好方法。有人能提供任何好的想法吗？
反转二叉树（从左到右）
39
- user1234831
6个回答
103
您可以使用递归。我们将一个节点的左右子节点就地交换，然后对其子节点执行相同的操作：
static void reverseTree(final TreeNode root) {
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
if (root.left != null) {
reverseTree(root.left);
}
if (root.right != null) {
reverseTree(root.right);
}
}
root可能为null的情况：static void reverseTree(final TreeNode root) {
if (root == null) {
return;
}
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
reverseTree(root.left);
reverseTree(root.right);
}
- Petar Ivanov
28
在C/C++中以O(1)的时间复杂度翻转一棵二叉树。
struct NormalNode {
int value;
struct NormalNode *left;
struct NormalNode *right;
};
struct ReversedNode {
int value;
struct ReversedNode *right;
struct ReversedNode *left;
};
struct ReversedNode *reverseTree(struct NormalNode *root) {
return (struct ReversedNode *)root;
}
- Zhipeng YANG
4
在 [tag:java] 中，那个转换是如何工作的？我认为你回答了一个不同的问题。 - Toby Speight
答案是正确的，但它不适用于Java，但在C / C ++中表现良好。 - Cewein
1这个回答让我开心地笑了。得爱上黑暗的 C++ 魔法 :D - Aviv Cohn
这不是在 C++ 的严格别名规则下违反了吗，因此导致未定义的行为？ - Alex O
5
这个问题有几个有趣的部分。首先，由于您使用的是Java语言，您最有可能拥有一个通用的Node 类，类似于以下内容：
class Node<T> {
private final T data;
private final Node left;
private final Node right;
public Node<T>(final T data, final Node left, final Node right) {
this.data = data;
this.left = left;
this.right = right;
}
....
}
其次，反转（有时称为倒置）可以通过改变节点的左右字段来完成，也可以通过创建一个与原始节点完全相同但其左右子节点已被“反转”的新节点来完成。前一种方法在另一个答案中展示，而后一种方法则在此处展示：
class Node<T> {
// See fields and constructor above...
public Node<T> reverse() {
Node<T> newLeftSubtree = right == null ? null : right.reverse();
Node<T> newRightSubtree = left == null ? null : left.reverse();
return Node<T>(data, newLeftSubtree, newRightSubtree);
}
}
不改变数据结构的想法是持久化数据结构背后的一个概念，这些数据结构非常有趣。
- Ray Toal
3
右边不应该是左反转，而左边是右反转吗？ - kapad
交换是在构建新节点时完成的：也就是为什么右边在左边之前。这并不清楚，因为构造函数没有被给出。 - amnn
很好的点子，@amnn，感谢您的初步编辑。Java缺少命名参数有点令人失望，如果能够说
new Node(data=data, left=right?.reverse(), right=left?.reverse())就太棒了，但是Java还没有实现这个功能。我们也可以这样实现:new Node().withData(data).withLeft(right.reverse.......).withRight(left.reverse......)等等。我最终只是通过使用命名局部变量使reverse方法更易读。 - Ray Toal0
递归函数可以非常简单，如下所示：
public Node flipTree(Node node) {
if(node == null) return null;
Node left = flipTree(node.left);
Node right = flipTree(node.right);
node.left = right;
node.right = left;
return node;
}
- Ajay Singh
2
2请不要仅仅回答代码。至少演示一下为什么它解决了问题，并且用文字或注释解释代码，以便未来的读者能够理解它。 - Adriaan
1公平地说，得票最高的答案也是仅有代码的。话虽如此，在添加自己的答案之前，值得先看一下已有的答案。你的答案与得票最高的答案完全相同，因此通常最好只是点赞那个答案，而不是添加重复的答案。 - aug
0
你可以按照以下方式递归地交换左右节点；
// helper method
private static void reverseTree(TreeNode<Integer> root) {
reverseTreeNode(root);
}
private static void reverseTreeNode(TreeNode<Integer> node) {
TreeNode<Integer> temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left != null)
reverseTreeNode(node.left);
if(node.right != null)
reverseTreeNode(node.right);
}
Java演示代码
import java.util.LinkedList;
import java.util.Queue;
public class InvertBinaryTreeDemo {
public static void main(String[] args) {
// root node
TreeNode<Integer> root = new TreeNode<>(6);
// children of root
root.left = new TreeNode<Integer>(3);
root.right = new TreeNode<Integer>(4);
// grand left children of root
root.left.left = new TreeNode<Integer>(7);
root.left.right = new TreeNode<Integer>(3);
// grand right childrend of root
root.right.left = new TreeNode<Integer>(8);
root.right.right = new TreeNode<Integer>(1);
System.out.println("Before invert");
traverseTree(root);
reverseTree(root);
System.out.println("\nAfter invert");
traverseTree(root);
}
// helper method
private static void reverseTree(TreeNode<Integer> root) {
reverseTreeNode(root);
}
private static void reverseTreeNode(TreeNode<Integer> node) {
TreeNode<Integer> temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left != null)
reverseTreeNode(node.left);
if(node.right != null)
reverseTreeNode(node.right);
}
// helper method for traverse
private static void traverseTree(TreeNode<Integer> root) {
Queue<Integer> leftChildren = new LinkedList<>();
Queue<Integer> rightChildren = new LinkedList<>();
traverseTreeNode(root, leftChildren, rightChildren);
System.out.println("Tree;\n*****");
System.out.printf("%3d\n", root.value);
int count = 0;
int div = 0;
while(!(leftChildren.isEmpty() && rightChildren.isEmpty())) {
System.out.printf("%3d\t%3d\t", leftChildren.poll(), rightChildren.poll());
count += 2;
div++;
if( (double)count == (Math.pow(2, div))) {
System.out.println();
count = 0;
}
}
System.out.println();
}
private static void traverseTreeNode(TreeNode<Integer> node, Queue<Integer> leftChildren, Queue<Integer> rightChildren) {
if(node.left != null)
leftChildren.offer(node.left.value);
if(node.right != null)
rightChildren.offer(node.right.value);
if(node.left != null) {
traverseTreeNode(node.left, leftChildren, rightChildren);
}
if(node.right != null) {
traverseTreeNode(node.right, leftChildren, rightChildren);
}
}
private static class TreeNode<E extends Comparable<E>> {
protected E value;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E value) {
this.value = value;
this.left = null;
this.right = null;
}
}
}
输出
Before invert
Tree;
*****
6
3 4
7 3 8 1
After invert
Tree;
*****
6
4 3
1 8 3 7
- Levent Divilioglu
-1
我看到大多数答案都没有关注空指针问题。
public static Node invertBinaryTree(Node node) {
if(node != null) {
Node temp = node.getLeftChild();
node.setLeftChild(node.getRightChild());
node.setRigthChild(temp);
if(node.left!=null) {
invertBinaryTree(node.getLeftChild());
}
if(node.right !=null) {
invertBinaryTree(node.getRightChild());
}
}
return node;
}
在上面的代码中，只有当根节点的左/右子节点不为空时，我们才进行递归调用。这是最快的方法之一！
- Sidd Thota
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接