70.翻转二叉树

题目

给你一棵二叉树的根节点 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

思路

每个节点都做同样一件事 -- 交换左右孩子

只要把每个节点的左孩子和右孩子都交换了，那每个节点都完成了自己的左右交换，整棵树就自然就翻转了。

用递归的思路:

翻转一棵树 = 交换根节点的左右孩子 + 翻转左子树 + 翻转右子树

同样，翻转左子树和翻转右子树都与翻转整棵树是同一个问题，只是规模变小了，这就是递归的标志。

递归的两要素:

1. 终止条件 当节点为空(null)时，没有东西可翻，直接返回null(或者说什么都不做)
2. 递推关系
   • 递归的翻转它的左子树和右子树
   • 交换它的左右孩子指针

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun invertTree(root: TreeNode?): TreeNode? {
        if (root == null) {
            return null
        }
        val tmp = root.left
        root.left = root.right
        root.right = tmp
        // 交换后再分别递归翻转
        invertTree(root.left)
        invertTree(root.right)
        return root
    }
}

复杂度

• 时间复杂度: O(n)：每个节点恰好被访问一次，执行一次常数时间的交换操作。
• 空间复杂度: O(h)：h 是树高，来自递归栈。最坏（退化成链）O(n)，平衡树 O(log n)。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!