实现二叉树反转：正确交换左子树和右子树

“纵有疾风来，人生不言弃”，这句话送给正在学习Golang的朋友们，也希望在阅读本文《实现二叉树反转：正确交换左子树和右子树》后，能够真的帮助到大家。我也会在后续的文章中，陆续更新Golang相关的技术文章，有好的建议欢迎大家在评论留言，非常感谢！

我很困惑如何在 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
    }

解决方案

您正在交换节点，而不是它们包含的值。就这样，所有的孩子都跟着来了。交换根的子节点后，“2”的子节点仍将是 4 和 5（一旦交换该节点的子节点，它们将是 5 和 4）。您正在“重新连接”整个结构，而不是拾取数字并将它们放在同一结构内的新位置。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《实现二叉树反转：正确交换左子树和右子树》文章吧，也可关注golang学习网公众号了解相关技术文章。