翻转一棵二叉树。

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
   4
   /   \
  7     2
 / \   / \
9   6 3   1

解答

• 递归 后序遍历

代码：

func invertTree(root *TreeNode) *TreeNode {
    if root==nil {// 递归结束条件
        return nil
    }

    // 当前需要一级需要做的是把 左节点指向右节点 右节点指向已经翻转的左节点
    temp := root.Left
    root.Left = root.Right
    root.Right = temp

    invertTree(root.Left) // 翻转的左节点
    invertTree(root.Right)// 返翻转的右节点

    return root
}

• 递归 前序遍历

func invertTree(root *TreeNode) *TreeNode {
    if root==nil {// 递归结束条件
        return nil
    }
    right:= invertTree(root.Right)// 返回已经翻转的右节点
    left := invertTree(root.Left) // 返回已经翻转的左节点
    // 当前需要一级需要做的是把 左节点指向已经翻转的右节点 右节点指向已经翻转的左节点
    root.Left = right
    root.Right = left
    return root
}