代码随想录算法训练营day15 | 102. 二叉树的层序遍历,226. 翻转二叉树,101. 对称二叉树

目录

102. 二叉树的层序遍历

226. 翻转二叉树

101. 对称二叉树

100. 相同的树


100是101的衍生题目。572也为101的衍生题目。

102. 二叉树的层序遍历

思路:

 以前的笔记

代码:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty())  {
            List<Integer> levelList = new LinkedList<>();
            int len = queue.size();
            // 遍历这一层
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                levelList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            list.add(levelList);
        }
        return list;
    }
}

226. 翻转二叉树

思路:

        本题目可以使用递归,迭代和层序遍历来做。需要注意的是迭代的方法中,只能使用前序和后序遍历,因为使用中序遍历会对同一个子树翻转两次。

代码:

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

//  DFS递归方法
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public void swapChildren(TreeNode node) {
        TreeNode tem = node.left;
        node.left = node.right;
        node.right = tem;
    }
}

// 迭代的前序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            swapChildren(node);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return root;
    }
        public void swapChildren(TreeNode node) {
        TreeNode tem = node.left;
        node.left = node.right;
        node.right = tem;
    }
}

// 层序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            swapChildren(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
        public void swapChildren(TreeNode node) {
        TreeNode tem = node.left;
        node.left = node.right;
        node.right = tem;
    }
}

101. 对称二叉树

思路:

        dfs:判断一个树是否对称,从根节点开始,看左子树和右子树是否对称。】

        bfs:通过队列进行遍历比较,把左子树根节点和右子树根节点入队列,比较因素同dfs。需要注意的是,后续入队列时,左子树的左节点和右子树的右节点,左子树的右节点和右子树的左节点一起入队,两两入队列,两两出队列比较。

代码:

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

// dfs
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }

    // 判断一个节点的左子树和右子树是否对称
    public boolean compare(TreeNode left, TreeNode right) {
        // 左子树和右子树都为空,对称
        if (left == null && right == null) {
            return true;
        }
        // 左右子树只有一个为空,不对称
        if (left == null || right == null) {
            return false;
        }
        // 左子树根节点值不等于右子树根节点值,不对称
        if (left.val != right.val) {
            return false;
        }
        // 只剩下left.val和right.val相等的情况
        // 需要判断left.left和right.right, left.right和right.left是否对称
        // boolean outside = compare(left.left, right.right);
        // boolean inside = compare(left.right, right.left);
        // return outside && inside;
        // 简化
        return compare(left.left, right.right) && compare(left.right, right.left);
    }
}

// bfs
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.right);
        queue.offer(root.left);
        while (!queue.isEmpty()) {
            TreeNode right = queue.poll();
            TreeNode left = queue.poll();

            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            // left.val等于right.val
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

这两道题目基本和本题是一样的,只要稍加修改就可以AC。

  • 100.相同的树(opens new window)
  • 572.另一个树的子树

100. 相同的树

 代码:

// dfs
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        } 

        // p.val和q.val相等的情况
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

// bfs
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }

            queue.offer(left.left);
            queue.offer(right.left);
            queue.offer(left.right);
            queue.offer(right.right);
        }
        return true;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/50149.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

卸载大脑,相信DFS

切莫相信动规&#xff0c;吾将为您指明前进之路 印子 比赛时&#xff0c;你是否有这样的经历&#xff1a;不敢用for暴搜&#xff0c;又不会用数学公式推理&#xff1b;焦急地在纸上打草&#xff0c;却没有优化思路&#xff1b;明明比赛前一天晚上背了那么多模板却脑子一片空白…

生成模型和判别模型工作原理介绍

您解决的大多数机器学习和深度学习问题都是从生成模型和判别模型中概念化的。在机器学习中,人们可以清楚地区分两种建模类型: 将图像分类为狗或猫属于判别性建模生成逼真的狗或猫图像是一个生成建模问题神经网络被采用得越多,生成域和判别域就增长得越多。要理解基于这些模型…

Python Web开发技巧VIII

目录 ModelSerializer和Serializer区别是什么 从queryset中取出某个models的字段值 Q对象进行模糊匹配 HTTP方式-如何模糊搜索JSON字段中的某个KEY值呢&#xff1f; showmigrations 合并两个或多个queryset ModelSerializer和Serializer区别是什么 都是DRF中用于序列化和…

QT【day3】

思维导图&#xff1a; 闹钟&#xff1a; //widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> // #include<QTime> //定时器 #include<QDebug> // #in…

力扣算法数学类—剑指 Offer 43. 1~n 整数中 1 出现的次数

目录 剑指 Offer 43. 1&#xff5e;n 整数中 1 出现的次数 题解&#xff1a; 代码&#xff1a; 结果&#xff1a; 输入一个整数 n &#xff0c;求1&#xff5e;n这n个整数的十进制表示中1出现的次数。 例如&#xff0c;输入12&#xff0c;1&#xff5e;12这些整数中包含1 的…

【雕爷学编程】MicroPython动手做(10)——零基础学MaixPy之神经网络KPU

早上百度搜“神经网络KPU”&#xff0c;查到与非网的一篇文章《一文读懂APU/BPU/CPU/DPU/EPU/FPU/GPU等处理器》&#xff0c;介绍各种处理器非常详细&#xff0c;关于“KPU”的内容如下&#xff1a; KPU Knowledge Processing Unit。 嘉楠耘智&#xff08;canaan&#xff09;号…

web流程自动化详解

今天给大家带来Selenium的相关解释操作 一、Selenium Selenium是一个用于自动化Web浏览器操作的开源工具和框架。它提供了一组API&#xff08;应用程序接口&#xff09;&#xff0c;可以让开发人员使用多种编程语言&#xff08;如Java、Python、C#等&#xff09;编写测试脚本&…

PS软件打开闪退是什么原因?怎么处理闪退的问题?

Photoshop简称PS&#xff0c;它作为图像处理专家&#xff0c;具有相当强大的功能&#xff0c;但是有小伙伴说不好用&#xff0c;因为打开后会闪退&#xff0c;那该怎么办呢&#xff1f; PS软件闪退的处理方法&#xff1a; 1.下载并安装Adobe Creative Cloud&#xff0c;再登录…

Vue3 word如何转成pdf代码实现

&#x1f642;博主&#xff1a;锅盖哒 &#x1f642;文章核心&#xff1a;word如何转换pdf 目录 1.前端部分 2.后端部分 在Vue 3中&#xff0c;前端无法直接将Word文档转换为PDF&#xff0c;因为Word文档的解析和PDF的生成通常需要在后端进行。但是&#xff0c;你可以通过Vu…

output delay 约束

output delay 约束 一、output delay约束概述二、output delay约束系统同步三、output delay约束源同步 一、output delay约束概述 特别注意&#xff1a;在源同步接口中&#xff0c;定义接口约束之前&#xff0c;需要用create_generated_clock 先定义送出的随路时钟。 二、out…

汽车交流充电桩控制主板的电路设计

汽车充电桩控制主板的电路设计 你是否曾经遇到过汽车没油的问题?但是&#xff0c;随着电动汽车的普及&#xff0c;充电问题也变得越来越重要。而汽车充电桩控制板电路设计则是解决这一问题的关键。 汽车充电桩控制板电路设计包括硬件电路设计、软件电路设计和安全性设计。硬件…

内网隧道代理技术(十三)之内网代理介绍

前言 什么?你问我内网隧道代理技术怎么突然就第十三篇了,第十二篇呢?这个,因为某些不可抗拒力量,第十二篇博客无法发表,如果想要查阅,请加内网渗透qq群:838076210 内网代理介绍 内网代理介绍 内网资产扫描这种场景一般是进行内网渗透才需要的代理技术,如果你不打内…

No104.精选前端面试题,享受每天的挑战和学习(小米)

文章目录 聊一下vue和react的区别react生命周期有哪些hooks解决了什么问题小程序跳转传参怎么传附录&#xff1a;「简历必备」前后端实战项目&#xff08;推荐&#xff1a;⭐️⭐️⭐️⭐️⭐️&#xff09; &#x1f4c8;「作者简介」&#xff1a;前端开发工程师 | 蓝桥云课签…

Jenkins 配置maven和jdk

前提:服务器已经安装maven和jdk 一、在Jenkins中添加全局变量 系统管理–>系统配置–>全局属性–>环境变量 添加三个全局变量 JAVA_HOME、MAVEN_HOME、PATH 二、配置maven 系统管理–>全局工具配置–>maven–>新增 新增配置 三、配置JDK 在系统管…

查看GPU使用的最佳方式

1. watch -n 1 nvidia-smi (最有名,没有之一) nvidia自带了一个nvidia-smi的命令行工具,会显示GPU使用情况 ​​​​​​​ 作为监控 GPU 的工具就显得有点过于简陋了。比如 Process name 栏只显示命令行的程序名,不显示参数,这样输出结果就是一堆 python 和 .../Minico…

2023年深圳杯数学建模C题无人机协同避障航迹规划

2023年深圳杯数学建模 C题 无人机协同避障航迹规划 原题再现&#xff1a; 平面上A、B两个无人机站分别位于半径为500 m的障碍圆两边直径的延长线上&#xff0c;A站距离圆心1 km&#xff0c;B站距离圆心3.5 km。两架无人机分别从A、B两站同时出发&#xff0c;以恒定速率10 m/s…

语音识别 — 特征提取 MFCC 和 PLP

一、说明 语音识别是一种技术&#xff0c;通过计算机和软件系统&#xff0c;将人们的口头语言转换为计算机可读的文本或命令。它使用语音信号处理算法来识别和理解人类语言&#xff0c;并将其转换为计算机可处理的格式。语音识别技术被广泛应用于许多领域&#xff0c;如语音助手…

WIZnet W6100-EVB-Pico 树莓派入门教程(一)

概述 W6100-EVB-Pico是基于树莓派RP2040和全硬件TCP/IP协议栈控制器W6100的微控制器评估板-基本工作原理与树莓派Pico板相同&#xff0c;但通过W6100芯片增加了以太网功能。 板载资源 RP2040是Raspberry Pi的首款微控制器。它将我们的高性能、低成本和易用性的标志性价值观带入…

【简历完善】- SLAM - 第一篇:卡尔曼滤波的学习

场景&#xff1a;晚上你需要从自己的卧室去上厕所&#xff0c;你知道家里的布局&#xff0c;了解自己的步长&#xff0c;但是没有灯。你如何才能走到厕所呢&#xff1f; 一些术语 “预测” “估计”。下面所说的预测和估计就是一回事。不同博客里面这两个词语大概意思也是一…

【Spring Boot】

目录 &#x1f36a;1 Spring Boot 的创建 &#x1f382;2 简单 Spring Boot 程序 &#x1f370;3 Spring Boot 配置文件 &#x1f36e;3.1 properties 基本语法 &#x1fad6;3.2 yml 配置文件说明 &#x1f36d;3.2.1 yml 基本语法 &#x1f369;3.3 配置文件里的配置类…