反转二叉树：如何正确交换整个左树和右树

Question

我很困惑如何在 golang 中正确交换二叉树。假设我们有低于 BST

Input BST1
     1
    / \
   2   3
  / \  / \
 4  5 6   7
/ \
8  9

...
output BST2
     1
    / \
   3   2
  / \  / \
 7  6 5   4
         / \
        9   8

...
Why not this? BST3
     1
    / \
   3   2
  / \  / \
 5  4 7   6
/ \
9  8

我发现下面的代码会输出正确答案，而且我知道交换 2 和 3 是可行的，因为树首先站在 1 处。但是，当我们开始递归时，我们将 tree 向左移动，现在无法交换左树的 4 和右树的 7，例如。由于每次我们进行递归（在 if tree.Left != nil 内），我们将节点向左移动，我不确定为什么我们可以交换树的左侧（如 4）节点和右侧（7）节点。至于我目前的理解，BST3` 似乎是正确的输出...

type BinaryTree struct {
    Value int

    Left  *BinaryTree
    Right *BinaryTree
}

func (tree *BinaryTree) InvertBinaryTree() {
    
    tree.Left, tree.Right = tree.Right, tree.Left
    if tree.Left != nil{
        tree.left.InvertBinaryTree
    }
    if tree.Right != nil {
        tree.Right.InvertBinaryTree
    }

Answer 1

您交换的是节点，而不是它们包含的值。因此，所有 children 都带有。交换根的 children 后，“2”的 children 仍将是 4 和 5（一旦交换该节点的 children，它们将是 5 和 4）。您是“re-wiring”整个结构，而不是拾取数字并将它们放在同一结构内的新位置。

反转二叉树：如何正确交换整个左树和右树

Invert Binary Tree: how to swap correctly entire left tree and right tree

go

binary-tree

binary-search-tree