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

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。但是，当我们开始递归时，我们向左移动，现在没有办法交换左树和右树，例如。由于每次我们经历递归（在 内部，我们将节点向左移动），我不确定为什么我们可以交换左树侧（如4）节点和右侧（7）节点。就我目前的理解来看，BST3'似乎是正确的输出...tree47if tree.Left != nil

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

您交换的是节点，而不是它们包含的值。因此，所有的孩子都来了。交换根的子级后，“2”的子项仍将是 4 和 5（一旦交换该节点的子级，它们将是 5 和 4）。你正在“重新连接”整个结构，而不是拿起数字并将它们放在同一结构中的新位置。