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

Question

我对如何在golang中正确交换二叉树感到困惑。假设我们有低于BSTInput 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 != niltype 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）。你正在“重新连接”整个结构，而不是拿起数字并将它们放在同一结构中的新位置。