反转二叉树（从左到右）[已关闭]

data-structures reverse java tree binary-tree

2022-09-01 03:25:46

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

例如，如果我们有二叉树

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

逆转它将创造

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

您可以看到新树是原始树的镜像。

我还没有想到一个关于如何解决这个问题的好实现。任何人都可以提供任何好主意吗？

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

要处理参数可能为 null 的情况，请执行以下操作：root

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

答案 2

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