反转二叉树(从左到右)

Question

我正在看面试问题,最近我遇到了一个问你如何反转一般二叉树的问题,比如从右到左翻转它.

例如,如果我们有二叉树

     6
   /   \
  3     4
 / \   / \
7   3 8   1

扭转它会创造

     6
   /   \
  4     3
 / \   / \
1   8 3   7

我还没有想到如何解决这个问题的良好实现.谁能提供任何好的想法？

谢谢

Answer 1

你可以使用递归:

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);
    }
}

根据评论:

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);
}

Answer 2

在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;
    }

Answer 3

这个问题有几个有趣的部分.首先,由于您的语言是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); 
    }
}

不改变数据结构的想法是持久性数据结构背后的思想之一,这非常有趣.