代码随想录算法训练营Day12 | Leetcode 226翻转二叉树、101对称二叉树、104二叉树的最大深度、111二叉树的最小深度

代码随想录算法训练营Day12 | Leetcode 226翻转二叉树、101对称二叉树、104二叉树的最大深度、111二叉树的最小深度

一、翻转二叉树

相关题目：Leetcode226
文档讲解：Leetcode226
视频讲解：Leetcode226

1. Leetcode226.翻转二叉树

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

  • 思路：
    • 翻转二叉树其实就相当于就把每一个节点的左右子节点交换。
      请添加图片描述
    • 递归法：
      • 确定递归函数的参数和返回值：参数就是要传入节点的指针，不需要其他参数了。
      • 确定终止条件：当前节点为空的时候，就返回。
      • 确定单层递归的逻辑：若是前序遍历，则先进行交换左右子节点，然后反转左子树，反转右子树。
    • 迭代法：
      • 深度优先遍历，与二叉树的迭代遍历相同，也可采用二叉树的统一迭代法。
      • 广度优先遍历，也就是层序遍历，层序遍历可以把每个节点的左右孩子都翻转一遍。
  • 递归法
#前序遍历：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Noneroot.left, root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return root#中序遍历：
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Noneself.invertTree(root.left)root.left, root.right = root.right, root.leftself.invertTree(root.left)return root#后序遍历：
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Noneself.invertTree(root.left)self.invertTree(root.right)root.left, root.right = root.right, root.leftreturn root
  • 迭代法
#前序遍历：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return None      stack = [root]        while stack:node = stack.pop()   node.left, node.right = node.right, node.left                   if node.right:stack.append(node.right)if node.left:stack.append(node.left)return root#伪中序遍历（结果是对的，看起来像是中序遍历，实际上它是前序遍历，只不过把中间节点处理逻辑放到了中间。还是要用'统一写法'才是真正的中序遍历）：
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return None      stack = [root]while stack:node = stack.pop()if node.right:stack.append(node.right)node.left, node.right = node.right, node.left # 放到中间，依然是前序遍历if node.right:stack.append(node.right)return root#伪后序遍历（结果是对的，看起来像是后序遍历，实际上它是前序遍历，只不过把中间节点处理逻辑放到了最后。还是要用'统一写法'才是真正的后序遍历）：
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Nonestack = [root]    while stack:node = stack.pop()if node.right:stack.append(node.right)if node.left:stack.append(node.left)node.left, node.right = node.right, node.left               return root
  • 广度优先遍历
#广度优先遍历（层序遍历）：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root: return Nonequeue = collections.deque([root])    while queue:node = queue.popleft()node.left, node.right = node.right, node.leftif node.left: queue.append(node.left)if node.right: queue.append(node.right)return root

二、对称二叉树

相关题目：Leetcode101、Leetcode100、Leetcode572
文档讲解：Leetcode101
视频讲解：Leetcode101

1. Leetcode101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

  • 思路：
    • 对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，其实要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
      请添加图片描述
    • 本题遍历只能是“后序遍历”，因为要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
    • 递归法：

      • 确定递归函数的参数和返回值：要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是 bool 类型。

      • 确定终止条件：首先要考虑两个节点为空的情况，节点为空的情况有：

        • 左节点为空，右节点不为空，不对称，return false。
        • 左不为空，右为空，不对称 return false。
        • 左右都为空，对称，返回 true。

        此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

        • 左右都不为空，比较节点数值，不相同就 return false。

      • 确定单层递归的逻辑：处理 左右节点都不为空，且数值相同的情况：

        • 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
        • 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
        • 如果左右都对称就返回 true ，有一侧不对称就返回 false 。
    • 迭代法：
      • 本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。可以使用队列来比较两个树（根节点的左右子树）是否相互翻转。（注意这不是层序遍历）
        请添加图片描述
  • 递归法
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truereturn self.compare(root.left, root.right)def compare(self, left, right):#首先排除空节点的情况if left == None and right != None: return Falseelif left != None and right == None: return Falseelif left == None and right == None: return True#排除了空节点，再排除数值不相同的情况elif left.val != right.val: return False#此时就是：左右节点都不为空，且数值相同的情况#此时才做递归，做下一层的判断outside = self.compare(left.left, right.right) #左子树：左、 右子树：右inside = self.compare(left.right, right.left) #左子树：右、 右子树：左isSame = outside and inside #左子树：中、 右子树：中 （逻辑处理）return isSame
  • 迭代法
#使用队列
import collections
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truequeue = collections.deque()queue.append(root.left) #将左子树头结点加入队列queue.append(root.right) #将右子树头结点加入队列while queue: #接下来就要判断这这两个树是否相互翻转leftNode = queue.popleft()rightNode = queue.popleft()if not leftNode and not rightNode: #左节点为空、右节点为空，此时说明是对称的continue#左右一个节点不为空，或者都不为空但数值不相同，返回falseif not leftNode or not rightNode or leftNode.val != rightNode.val:return Falsequeue.append(leftNode.left) #加入左节点左孩子queue.append(rightNode.right) #加入右节点右孩子queue.append(leftNode.right) #加入左节点右孩子queue.append(rightNode.left) #加入右节点左孩子return True#使用栈
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truest = [] #这里改成了栈st.append(root.left)st.append(root.right)while st:rightNode = st.pop()leftNode = st.pop()if not leftNode and not rightNode:continueif not leftNode or not rightNode or leftNode.val != rightNode.val:return Falsest.append(leftNode.left)st.append(rightNode.right)st.append(leftNode.right)st.append(rightNode.left)return True

三、二叉树的最大深度

相关题目：Leetcode104、Leetcode559
文档讲解：Leetcode104
视频讲解：Leetcode104

1. Leetcode104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

  • 思路：

    • 本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。根节点的高度就是二叉树的最大深度。
      • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
      • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
    • 递归法（后序遍历）：
      • 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
      • 确定终止条件：如果为空节点的话，就返回 0，表示高度为 0。
      • 确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
    • 迭代法：
      使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

  • 递归法

##104.二叉树的最大深度
class Solution:def maxdepth(self, root: treenode) -> int:return self.getdepth(root)def getdepth(self, node):if not node:return 0leftheight = self.getdepth(node.left) #左rightheight = self.getdepth(node.right) #右height = 1 + max(leftheight, rightheight) #中return height#精简代码
class Solution:def maxdepth(self, root: treenode) -> int:if not root:return 0return 1 + max(self.maxdepth(root.left), self.maxdepth(root.right))##559.n叉树的最大深度
class Solution:def maxDepth(self, root: 'Node') -> int:if not root:return 0max_depth = 1for child in root.children:max_depth = max(max_depth, self.maxDepth(child) + 1)return max_depth
  • 层序遍历
##104.二叉树的最大深度
class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0queue = collections.deque([root])while queue:depth += 1for _ in range(len(queue)):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth##559.n叉树的最大深度
class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0queue = collections.deque([root])while queue:depth += 1for _ in range(len(queue)):node = queue.popleft()for child in node.children:queue.append(child)return depth

四、二叉树的最小深度

相关题目：Leetcode111
文档讲解：Leetcode111
视频讲解：Leetcode111

1. Leetcode111.二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度 是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

  • 思路：

    • 左右孩子都为空的节点才是叶子节点：
      请添加图片描述
    • 递归法：
      • 确定递归函数的参数和返回值：参数为要传入的二叉树根节点，返回的是int类型的深度。
      • 确定终止条件：终止条件也是遇到空节点返回 0，表示当前节点的高度为 0。
      • 确定单层递归的逻辑：
        • 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
        • 如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
        • 如果左右子树都不为空，返回左右子树深度最小值 + 1 。
    • 迭代法：
      可以使用层序遍历，需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点。

  • 注意：

    • 在递归法的单层递归逻辑中，如果直接像 Leetcode104.二叉树的最大深度 那样返回左右子树深度最小值 + 1 ，则前述图中最小深度会计算为 1，因为根节点的左子树为空，直接返回最小深度。

  • 递归法

class Solution:def getDepth(self, node):if node is None:return 0leftDepth = self.getDepth(node.left)  # 左rightDepth = self.getDepth(node.right)  # 右# 当一个左子树为空，右不为空，这时并不是最低点if node.left is None and node.right is not None:return 1 + rightDepth# 当一个右子树为空，左不为空，这时并不是最低点if node.left is not None and node.right is None:return 1 + leftDepthresult = 1 + min(leftDepth, rightDepth)return resultdef minDepth(self, root):return self.getDepth(root)#精简
class Solution:def minDepth(self, root):if root is None:return 0if root.left is None and root.right is not None:return 1 + self.minDepth(root.right)if root.left is not None and root.right is None:return 1 + self.minDepth(root.left)return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
  • 迭代法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0queue = collections.deque([root])while queue:depth += 1 for _ in range(len(queue)):node = queue.popleft()if not node.left and not node.right:return depthif node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

3.26学习总结 做题

3.26学习总结 做题

先初始化n1时，输出的图案。 观察可以得到，n每加1，则在原先图案的左下方和右下方重新打印一遍原先的图案，可以分为两步。 1.复制原先图案打印在其正下方和右下方，并将原先图案清空。 2.在现在图案的上方中间打印原先…
阅读更多...
Linux学习笔记（应用篇二）

Linux学习笔记（应用篇二）

基于I.MX6ULL.MINI开发板 开发板与电脑相互通信电脑与开发板互传文件 开发板与电脑相互通信 用网线将电脑与开发板连接 本人使用的是Ubuntu系统，不是虚拟机 一般来说刚开始电脑和开发板是ping不通的 首先查看电脑的 IP WinR，cmd调出终端 我使用的是…
阅读更多...
【gradio】从零搭建知识库问答系统-Gradio+Ollama+Qwen2.5实现全流程

【gradio】从零搭建知识库问答系统-Gradio+Ollama+Qwen2.5实现全流程

从零搭建大模型问答系统-GradioOllamaQwen2.5实现全流程（一） 前言一、界面设计（计划）二、模块设计1.登录模块2.注册模块3. 主界面模块4. 历史记录模块 三、相应的接口（前后端交互）四、实现前端界面的设计co…
阅读更多...
中间件漏洞-Tomcat篇

中间件漏洞-Tomcat篇

一：CVE-2017-12615 1.搭建服务 cd /www/wwwroot/vulhub-master/tomcat/CVE-2017-12615 docker-compose up -d 2.打开网页 3.在哥斯拉中生成jsp木马并保存为2.jpg 对当前页面进行抓包，修改提交方式为PUT并复制木马 4.在网页中访问我们生成的木马&#…
阅读更多...
PHP eval 长度限制绕过与 Webshell 获取

PHP eval 长度限制绕过与 Webshell 获取

在 PHP 代码中&#xff0c;如果 eval($param); 存在且长度受限&#xff0c;并且过滤了 eval 和 assert&#xff0c;仍然可以通过多种方法绕过限制&#xff0c;获取 Webshell。 源码 <?php $param $_REQUEST[param]; if(strlen($param)<17 && stripos($param,…
阅读更多...
31天Python入门——第15天:日志记录

31天Python入门——第15天:日志记录

你好&#xff0c;我是安然无虞。 文章目录 日志记录python的日志记录模块创建日志处理程序并配置输出格式将日志内容输出到控制台将日志写入到文件 logging更简单的一种使用方式 日志记录 日志记录是一种重要的应用程序开发和维护技术, 它用于记录应用程序运行时的关键信息和…
阅读更多...
特殊行车记录仪DAT视频丢失的恢复方法

特殊行车记录仪DAT视频丢失的恢复方法

行车记录仪是一种常见的车载记录仪&#xff0c;和常见的“小巧玲珑”的行车记录仪不同&#xff0c;一些特种车辆使用的记录仪的外观可以用“笨重”来形容。下边我们来看看特种车载行车记录仪删除文件后的恢复方法。 故障存储: 120GB存储设备/文件系统:exFAT /簇大小:128KB 故…
阅读更多...
机器学习——KNN数据均一化

机器学习——KNN数据均一化

在KNN&#xff08;K-近邻&#xff09;算法中&#xff0c;数据均一化&#xff08;归一化&#xff09;是预处理的关键步骤&#xff0c;用于消除不同特征量纲差异对距离计算的影响。以下是两种常用的归一化操作及其核心要点&#xff1a; 质押 一 、主要思想 1. 最值归一化&#…
阅读更多...
Element UI实现表格全选、半选

Element UI实现表格全选、半选

制作如图所示的表格全选、半选&#xff1a; 父组件 <template><div id"app"><SelectHost :hostArray"hostArray" /></div> </template><script> import SelectHost from ./components/SelectHost.vue export default…
阅读更多...
深度学习入门1 基于Python的理论与实现

深度学习入门1 基于Python的理论与实现

torch.unsqueeze()将一维数据变为二维数据&#xff0c;torch只能处理二维数据 tensor不能反向&#xff0c;variable可以反向。variable.data.numpy()转换为numpy 第3章 神经网络 实现softmax函数时的注意事项&#xff1a;为防止e的指数运算造成溢出 矩阵的第 0 维是列方向,第…
阅读更多...
vue响应式原理剖析

vue响应式原理剖析

一、什么是响应式？ 我们先来看一下响应式意味着什么？我们来看一段代码： m有一个初始化的值，有一段代码使用了这个值； 那么在m有一个新的值时，这段代码可以自动重新执行； let m = 20 console.log(m) console.log(m * 2)m = 40上面的这样一种可以自动响应数据变量的代码机…
阅读更多...
UDP数据报套接字编程

UDP数据报套接字编程

1.DatagramSocket API Socket是操作系统中的一个概念 本质上是一种特殊的文件 Socket就属于是把"网卡"这个设备,抽象成文件了 往Socket文件中写数据,就相当于通过网卡发送数据 从Socket文件读数据,就相当于通过网卡接受数据 在Java中就使用DatagramSocket这个类…
阅读更多...
逼用户升级Win11，微软开始给Win10限速

逼用户升级Win11，微软开始给Win10限速

随着Windows10的支持时间越来越短&#xff0c;微软也加大了对Win10用户的驱赶力度。 最近&#xff0c;微软官宣了将要在今年6月份降低OneNote for Windows 10的同步速度。软件也将和Windows10在今年的10月14日一同停止支持和维护。 这将影响实时协作和多设备访问。 对OneNote…
阅读更多...
NodeJs之http模块

NodeJs之http模块

一、概念&#xff1a; 1、协议&#xff1a;双方必须共同遵从的一组约定。 Hypertext Transfer Protocol&#xff1a;HTTP&#xff0c;超文本传输协议 2、请求&#xff1a; ① 请求报文的组成&#xff1a; 请求行请求头空行请求体 ② 请求行&#xff1a;
阅读更多...
26考研——图_图的应用（6）

26考研——图_图的应用（6）

408答疑 文章目录 四、图的应用图的应用考查形式最小生成树最小生成树概念最小生成树的性质最小生成树中某顶点到其他顶点是否具有最短路径的分析构造最小生成树的算法Prim 算法Prim 算法概述Prim 算法的构建思想Prim 算法的步骤Prim 算法的示例Prim 算法的性质 Kruskal 算法Kr…
阅读更多...
Photoshop 2025安装包下载及Photoshop 2025详细图文安装教程

Photoshop 2025安装包下载及Photoshop 2025详细图文安装教程

文章目录 前言一、Photoshop 2025安装包下载二、Photoshop 2025安装教程1.解压安装包2.运行程序3.修改安装路径4.设安装目录5.开始安装6.等安装完成7.关闭安装向导8.启动软件9.安装完成 前言 无论你是专业设计师&#xff0c;还是初涉图像处理的小白&#xff0c;Photoshop 2025…
阅读更多...
MySQL-存储过程

MySQL-存储过程

介绍 基本语法 创建 调用 查看 删除 变量 系统变量 查看 设置 用户定义变量 赋值 使用 局部变量 声明 赋值 流程控制 参数 条件结构 IF case 循环结构 while repeat loop 游标 条件处理程序 介绍 举个简单的例子&#xff0c;我们先select某数据&…
阅读更多...
debug 笔记：llama 3.2 部署bug 之cutlassF: no kernel found to launch!

debug 笔记：llama 3.2 部署bug 之cutlassF: no kernel found to launch!

1 问题描述 按照官方的写法 import torch from transformers import pipeline import os os.environ["HF_TOKEN"] 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 model_id "meta-llama/Llama-3.2-3B"pipe pipeline("text-generation", modelmode…
阅读更多...
《Python实战进阶》No34：卷积神经网络（CNN）图像分类实战

《Python实战进阶》No34：卷积神经网络（CNN）图像分类实战

第34集&#xff1a;卷积神经网络&#xff08;CNN&#xff09;图像分类实战 摘要 卷积神经网络&#xff08;CNN&#xff09;是计算机视觉领域的核心技术&#xff0c;特别擅长处理图像分类任务。本集将深入讲解 CNN 的核心组件&#xff08;卷积层、池化层、全连接层&#xff09;…
阅读更多...
【银河麒麟系统常识】命令：uname -m（查看系统架构）

【银河麒麟系统常识】命令：uname -m（查看系统架构）

命令&#xff1a; uname -m 功能 常用的 Linux/Unix 终端命令&#xff0c;用于显示当前系统的硬件架构&#xff1b; 返回 返回系统的CPU架构类型&#xff0c;用于判断软件兼容性&#xff1b; 输出结果架构说明常见设备x86_64Intel/AMD 64位 CPU主流 PC、服务器aarch64ARM 64位 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023