400网站推广公司网站开发与维护

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;}
}