226. 翻转二叉树【58】

深碍√TFBOYSˉ_ 2023-09-27 18:16 140阅读 0赞

> **难度等级：容易**

> **上一篇算法：**
> 
> [543. 二叉树的直径【71】][543. _71]

> **力扣此题地址：**
> 
> [226. 翻转二叉树 - 力扣（Leetcode）][226. _ - _Leetcode]

## 1.题目：226. 翻转二叉树 ##

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

![41adbd1af3e44334a5872aab9d2d2cfb.png][]

## 2.解题思路： ##

> 遇到二叉树的算法题，就知道要用**递归**的方式来解决
> 
> 这里要求的是翻转二叉树，除了根节点，每个节点都有翻转， 仔细看下题目的 **输入** 和 **输出**，输出的左右子树的位置跟输入正好是相反的，于是我们可以递归的交换左右子树来完成这道题。 看一下动画就明白了：
> 
> ![ebbc927511d3a45c2134ee376380dda1.gif][]
> 
> **其实就是交换一下左右节点，然后再递归的交换左节点，右节点 根据动画图我们可以总结出递归的两个条件如下：**
> 
>  *  终止条件：当前节点为 null 时返回
>  *  交换当前节点的左右子节点，再递归的交换当前节点的左子节点的左右子节点，递归的交换当前节点的右子节点的左右子节点
> 
> 思路参考：[226. 翻转二叉树 - 力扣（Leetcode）][226. _ - _Leetcode 1]

## 3.代码实现： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
    	public TreeNode invertTree(TreeNode root) {
    		if(root==null) {//递归函数的终止条件，节点为空时返回
    			return null;
    		}
    		
            //下面三句是将当前节点的左右子树交换
    		TreeNode tmp = root.right;
    		root.right = root.left;
    		root.left = tmp;
    		
    		invertTree(root.left);//递归交换当前节点的 左子树
    		invertTree(root.right);//递归交换当前节点的 右子树
    		
            //函数返回时就表示当前这个节点，以及它的左右子树,都已经交换完了
    		return root;
    	}
    }

[543. _71]: https://blog.csdn.net/m0_51697147/article/details/130470484?spm=1001.2014.3001.5501
[226. _ - _Leetcode]: https://leetcode.cn/problems/invert-binary-tree/description/
[41adbd1af3e44334a5872aab9d2d2cfb.png]: https://img-blog.csdnimg.cn/41adbd1af3e44334a5872aab9d2d2cfb.png
[ebbc927511d3a45c2134ee376380dda1.gif]: https://img-blog.csdnimg.cn/img_convert/ebbc927511d3a45c2134ee376380dda1.gif
[226. _ - _Leetcode 1]: https://leetcode.cn/problems/invert-binary-tree/solutions/73159/dong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua/