二叉树的镜像

Java基础

浏览数:131

2019-3-22

AD:资源代下载服务

前言

牛客网剑指offer的66道题,刷起来!每道题会提供简单的思路以及测试通过的代码

题目描述

二叉树结构:

 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

注:点击左下角的阅读原文即可跳转到原文,可以提交代码

解答思路

在上题中我说了对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的。而且解法还都非常相似,没看过上道题的或许可以看一下:

如果你递归学了还不错的话,这道题用递归会很简单,我们假设函数 Mirror() 就是求源二叉树的镜像。

刚开始的源二叉树:

那么我们可以先对根节点的左右子树进行镜像化:

left = Mirror(root.left);

right = Mirror(root.right);

镜像化之后的结果:

之后我们只需要将 root 的左右节点进行交换即可

代码如下:

public class 二叉树的镜像 {
    public void Mirror(TreeNode root) {
        if(root == null)
            return;
        root = solve(root);
    }
    private TreeNode solve(TreeNode root) {
        if(root == null)
            return root;
        // 递归先把左右节点镜像化
        TreeNode left = solve(root.left);
        TreeNode right = solve(root.right);
        // 对左右子树进行交换。
        root.left = right;
        root.right = left;
        return root;
    }
}