【刷题笔记10.6】LeetCode：翻转二叉树

LeetCode：翻转二叉树

一、题目描述

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

二、分析

我们在做二叉树题目时候，第一想到的应该是用 递归 来解决。 仔细看下题目的 输入 和 输出，输出的左右子树的位置跟输入正好是相反的，于是我们可以递归的交换左右子树来完成这道题。

其实就是交换一下左右节点，然后再递归的交换左节点，右节点。
我们可以总结出递归的两个条件如下：

• 终止条件：当前节点为 null 时返回
• 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点

三、代码实现

public class Deal13 {
    public TreeNode invertTree(TreeNode root) {
        //1、递归函数的终止条件，节点为null时返回
        if (root == null) {
            return null;
        }

        //2、下面三句是将当前节点的左右子树交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        //3.1、递归交换当前节点的 左子树
        invertTree(root.left);
        //3.2、递归交换当前节点的 右子树
        invertTree(root.right);

        //4、函数返回时就表示当前这个节点，以及它的左右子树都已经交换完成
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22