专栏首页码上积木LeetCode题解—二叉树的镜像

LeetCode题解—二叉树的镜像

前言

五一快乐老铁们,祝大家假期愉快~

然后说个事,以后可能会减少算法题的文章了,因为我对于算法也没有很深的理解,只是和大家分享一下我刷题的过程,所以可能对大家的帮助不大。

一周两更Android系列肯定不会变,然后剩下的一篇我会慢慢尝试新的内容形式,再想想看吧。

今天的算法题目是 二叉树的镜像。

题目

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

示例 1:输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]

限制:0 <= 节点个数 <= 1000

解法一

登登,其实这道题的精髓就在于每个子树的左右节点都进行了替换,就完成了一个镜像。所以我们可以通过递归的方式,交换每个左右子节点。

当节点为null,返回null,否则就返回传进来的节点。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        //继续处理下面的节点
        TreeNode leftRoot = mirrorTree(root.right);
        TreeNode rightRoot = mirrorTree(root.left);
        //交换左右节点
        root.left = leftRoot;
        root.right = rightRoot;
        return root;
    }
}

复杂度

时间复杂度:O(n) 空间复杂度:O(n)。(递归使用栈空间)

解法二

利用集合来遍历树的每个节点,然后将每个节点的左右节点交换,一直到所有节点都完成即可。

这里用栈的方式进行处理:

public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        //根节点入栈
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        //遍历每个节点
        while(!stack.isEmpty()) {
            //出栈一个节点
            TreeNode node = stack.pop();
            //添加左右子节点
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            //交换左右节点
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }

复杂度

时间复杂度:O(n) 空间复杂度:O(n)

参考

https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof

本文分享自微信公众号 - 码上积木(Lzjimu),作者:积木zz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [剑指offer] 二叉树的镜像

    通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

    尾尾部落
  • 镜像二叉树

    一份执着✘
  • LeetCode 剑指Offer 面试题27. 二叉树的镜像

    输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]

    TrueDei
  • 相同的树、对称二叉树、翻转二叉树

    木子星兮
  • LeetCode25|二叉树的镜像

    5,总结,对于树结构一般都是都可以转换为递归结构进行解决,这是之前做题感觉到的,有的时候也会按照这些思路进行解决,有的时候自己没有很多文字在这里唠嗑什么,因为一...

    码农王同学
  • Day18:二叉树的镜像

      由于本题的本质就是考察二叉树,因此还是得用到递归的方法。其实本题就是将二叉树的左右子树进行交换即可。因此我们可以从根节点开始遍历,如果遍历的节点有子结点,就...

    一计之长
  • BAT 经典算法笔试题: 镜像二叉树

    再过不到 2 个月,互联网行业就要再次迎来面试高峰了。为了让大家能顺利通过所有面试环节必经的笔试阶段,我提前给大伙准备了一套常见的算法笔试题。这套算法题来源于 ...

    老钱
  • 【leetcode】21.多数元素

    为了回馈各位粉丝,礼尚往来,给大家准备了一条多年积累下来的优质资源,包括 学习视频、面试资料、珍藏电子书等

    一条IT
  • leetcode树之对称二叉树

    这里采用递归的方式解决,定义一个compare,然后对比left及right节点,若二者都为null返回true,若其中一个不为null或者值不相等则返回fal...

    codecraft
  • leetcode树之对称二叉树

    这里采用递归的方式解决,定义一个compare,然后对比left及right节点,若二者都为null返回true,若其中一个不为null或者值不相等则返回fal...

    codecraft
  • 每天一道leetcode-101对称二叉树

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • LeetCode题解—二叉树

    听名字还是比较好理解的,就是每个节点有两个分叉的树。但是又不要求一定有两个节点,只要小于等于2个节点就可以。

    码上积木
  • DFS基础问题-LeetCode 98、101(二叉树中序遍历,层次遍历)

    假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

    算法工程师之路
  • 【leetcode刷题】T114-对称二叉树

    https://leetcode-cn.com/problems/symmetric-tree/

    木又AI帮
  • Swift 对称二叉树 - LeetCode

    就像人站在镜子前审视自己那样。镜中的反射与现实中的人具有相同的头部,但反射的右臂对应于人的左臂,反之亦然。

    韦弦zhy
  • 【算法专栏】对称的二叉树

    请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

    ConardLi
  • 剑指 Offer 27. 二叉树的镜像

    大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面...

    五分钟学算法
  • 总结了一些算法二叉树操作的干货 (附Python代码)

    导读:二叉树是一种经典的数据结构,其概念本身不难理解,但因其结构的特殊性,许多操作都有着非常精妙的技巧。结合最近LeetCode中的一些相关题目,简要记录一些个...

    程序IT圈
  • 总结了一些二叉树操作的干货……

    导读:二叉树是一种经典的数据结构,其概念本身不难理解,但因其结构的特殊性,许多操作都有着非常精妙的技巧。结合最近LeetCode中的一些相关题目,简要记录一些个...

    luanhz

扫码关注云+社区

领取腾讯云代金券