226.翻转二叉树

力扣传送门(opens new window)

翻转一棵二叉树。

给你一棵二叉树的根节点 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 = []
输出：[]

解题思路：

下面看一下具体的解题步骤：

1、首先确定递归函数的参数和返回值

参数就是要传入根节点，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode。

public TreeNode invertTree(TreeNode root) {}

2.确定终止条件

当前节点为空的时候，就返回

![pexels-jeffry-surianto-18152898.jpg](https://cdn.amarantos-blog.cn/halo/res/pexels-jeffry-surianto-18152898.jpg)if (root == NULL) return root;

3.因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

TreeNode temp = root.left; // 保存左子节点的引用
        root.left = root.right; // 将右子节点赋值给左子节点
        root.right = temp; // 将保存的左子节点赋值给右子节点
        dfs(root.left); // 递归反转左子树
        dfs(root.right); // 递归反转右子树

也就是交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点。

代码实现：

/**
 * 二叉树节点的定义
 */
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; // 如果根节点为空，直接返回null
        }
        dfs(root); // 调用深度优先搜索方法
        return root; // 返回反转后的二叉树的根节点
    }

    // 深度优先搜索方法
    public void dfs(TreeNode root){
        if(root == null){
            return; // 如果节点为空，直接返回
        }
        TreeNode temp = root.left; // 保存左子节点的引用
        root.left = root.right; // 将右子节点赋值给左子节点
        root.right = temp; // 将保存的左子节点赋值给右子节点
        dfs(root.left); // 递归反转左子树
        dfs(root.right); // 递归反转右子树
    }
}