题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入： root = [4,2,7,1,3,6,9]
输出： [4,7,2,9,6,3,1]

示例 2：

输入： root = [2,1,3]
输出： [2,3,1]

示例 3：

输入： root = []
输出： []

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

代码及注释

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func invertTree(root *TreeNode) *TreeNode {
    // 如果根节点为空，直接返回
    if root == nil {
        return nil
    }
    // 递归地反转左子树和右子树
    left := invertTree(root.Left)
    right := invertTree(root.Right)

    // 交换左右子树
    root.Left = right
    root.Right = left
    return root
}

代码解释

1. 空节点检查:

   if root == nil {
       return nil
   }
   

   • 如果当前节点 root 为空，直接返回 nil。

2. 递归反转左右子树:

   left := invertTree(root.Left)
   right := invertTree(root.Right)
   

   • 使用递归的方法反转左子树和右子树。

3. 交换左右子树:

   root.Left = right
   root.Right = left
   

   • 交换左子树和右子树。

整个函数的逻辑很简单，它首先递归地反转左右子树，然后交换左右子树。最后返回反转后的根节点。

这个递归的解法的时间复杂度是 O(n)，其中 n 是二叉树的节点数。