当前位置:网站首页>二叉树 | 递归遍历 | leecode刷题笔记
二叉树 | 递归遍历 | leecode刷题笔记
2022-08-10 22:22:00 【Begonia_cat】
文章目录
跟随carl代码随想录刷题
语言:python
递归法与迭代法哪个更好呢?
- 递归法
空间复杂度
大一些,因为递归需要系统堆栈存参数返回值等等。- 递归
更容易让程序员理解
,但收敛不好,容易栈溢出。- 递归是
方便了程序员
,难为了机器
(各种保存参数,各种进栈出栈)。- ️在实际项目开发的过程中我们是要
尽量避免递归
!因为项目代码参数、调用关系都比较复杂,不容易控制递归深度,甚至会栈溢出。——代码随想录
二叉树的递归遍历——深度优先
- 递归的实现就是:每一次递归调用都会把函数的
局部变量、参数值和返回地址
等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数。 - 三要素:
- 确定递归函数的参数和返回值
def traversal(root: TreeNode):
# 前序遍历
- 确定终止条件
if (root == None) return;
如果当前遍历的节点为空就返回
- 确定单层递归的逻辑
result.append(root.val)
# 中traversal(root.left)
# 左traversal(root.right)
# 右
- 确定递归函数的参数和返回值
- ️
前序遍历
、中序遍历
、后序遍历
代码的唯一区别就是:中、左、右三个子句的顺序区别。
144. 二叉树的前序遍历
题目:给你二叉树的根节点 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 1. 初始化一个列表用于后续存放结果
result = []
# 2. 定义前序遍历的递归过程
def traversal(root:TreeNode):
if root == None:
return
result.append(root.val)
traversal(root.left)
traversal(root.right)
# 3. 调用前序遍历的递归函数
traversal(root)
# 4. 结果集
return result
94. 二叉树的中序遍历
题目:给定一个二叉树的根节点 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 1. 初始化一个列表用于存放结果集
result = []
# 2. 中序遍历的函数
def traversal(root:TreeNode):
if root == None:
return
traversal(root.left)
result.append(root.val)
traversal(root.right)
# 3. 调用中序遍历函数
traversal(root)
# 4. 返回结果集
return result
145. 二叉树的后序遍历
题目:给你一棵二叉树的根节点 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 1. 初始化一个列表用于存放结果集
result = []
# 2. 中序遍历的函数
def traversal(root:TreeNode):
if root == None:
return
traversal(root.left)
traversal(root.right)
result.append(root.val)
# 3. 调用中序遍历函数
traversal(root)
# 4. 返回结果集
return result
N叉树的递归遍历
589. N 叉树的前序遍历
题目:给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。
题目分析
和二叉树的写法几乎一样,唯一区别:for ch in root.children: traversal(ch)
完整代码如下
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
class Solution:
def preorder(self, root: 'Node') -> List[int]:
# 1. 初始化一个列表用于后续存放结果
result = []
# 2. 定义前序遍历的递归过程
def traversal(root):
if root == None:
return
result.append(root.val)
for ch in root.children:
traversal(ch)
# traversal(root.right)
# 3. 调用前序遍历的递归函数
traversal(root)
# 4. 结果集
return result
590. N 叉树的后序遍历
题目:给定一个 n 叉树的根节点 root ,返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。
输入:root = [1,null,3,2,4,null,5,6]
输出:[5,6,3,2,4,1]
题目分析
- 和二叉树的写法几乎一样,唯一区别:
for ch in root.children: traversal(ch)
- 只用在上一题
N叉树的前序遍历
的基础上调换代码位置,即可实现后序遍历。
完整代码如下
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
class Solution:
def postorder(self, root: 'Node') -> List[int]:
# 1. 定义空列表用于存放结果集
result = []
# 2. 定义函数
def traversal(root):
if root == None:
return
for ch in root.children:
traversal(ch)
result.append(root.val)
# 调用函数
traversal(root)
# 返回函数
return result
边栏推荐
- QT笔记——QT工具uic,rcc,moc,qmake的使用和介绍
- 测试4年感觉和1、2年时没什么不同?这和应届生有什么区别?
- IM 即时通讯开发如何设计图片文件的服务端存储架构
- RK3399 platform development series explanation (kernel-driven peripherals) 6.35, IAM20680 gyroscope introduction
- 高学历毕业生,该学单片机还是plc?
- Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
- MySQL学习笔记(2)——简单操作
- BM13判断一个链表是否为回文结构
- STL-stack
- 罗克韦尔AB PLC RSLogix5000中计数器指令使用方法介绍
猜你喜欢
MySQL学习笔记(1)——基础操作
How to be a Righteous Hacker?What should you study?
Qualcomm Platform Development Series Explanation (Application) Introduction to QCMAP Application Framework
DC-7靶场下载及渗透实战详细过程(DC靶场系列)
高通平台开发系列讲解(应用篇)QCMAP应用框架介绍
自学软件测试不知道该如何学起,【软件测试技能图谱|自学测试路线图】
VLAN huawei 三种模式
Pro-test is effective | A method to deal with missing features of risk control data
How many threads does LabVIEW allocate?
How to translate financial annual report, why choose a professional translation company?
随机推荐
August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
【Maui正式版】创建可跨平台的Maui程序,以及有关依赖注入、MVVM双向绑定的实现和演示
BM7 链表中环的入口结点
SDP
Research on multi-element N-k fault model of power system based on AC power flow (implemented by Matlab code) [Power System Fault]
port forwarding
RecyclerView滑动监听
音乐播放器(未完成版本)
Splunk中解决数据质量问题常见日期格式化
字节跳动原来这么容易就能进去...
3598. Binary tree traversal (Huazhong University of Science and Technology exam questions)
How many threads does LabVIEW allocate?
BM13判断一个链表是否为回文结构
A shell script the for loop statements, while statement
JS中使用正则表达式g模式和非g模式的区别
实例055:按位取反
Detailed installation steps and environment configuration of geemap
Power system power flow calculation (Newton-Raphson method, Gauss-Seidel method, fast decoupling method) (Matlab code implementation)
STL-deque
CIKM2022 | 基于双向Transformers对比学习的序列推荐