☆打卡算法☆LeetCode 145. 二叉树的后序遍历 算法解析

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: ☆打卡算法☆LeetCode 145. 二叉树的后序遍历 算法解析

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定二叉树的根节点,完成后序遍历。”

2、题目描述

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

1702361235676.jpg

示例 1:
输入: root = [1,null,2,3]
输出: [3,2,1]
示例 2:
输入: root = [1]
输出: [1]

二、解题

1、思路分析

二叉树的后序遍历也讲过很多遍了。

也就是按照左子树→右子树→根节点的方式遍历这棵树。

在访问整个树的时候,也是同样的方式遍历,知道遍历整个树。

遍历过程具有递归性质,可以使用递归函数来模拟这一过程。

2、代码实现

代码参考:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

1702361266541.jpg


3、时间复杂度

时间复杂度:O(n)

其中n是二叉树的节点数,每个节点会被访问一次。

空间复杂度:O(n)

其中n是二叉树的节点数,主要是递归过程在栈上的开销。

三、总结

首先实现一个递归函数来遍历整个树。

在递归调用的时候,先将左子树传入,遍历左子树,然后将右子树传入,遍历右子树。

最后将root节点的值加入答案即可。

遍历终止条件为碰到空节点

相关文章
|
15天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
34 0
|
9天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
27 3
|
10天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
16天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-RMSprop算法解析
关注B站【肆十二】,观看更多实战教学视频。本期介绍深度学习中的RMSprop优化算法,通过调整每个参数的学习率来优化模型训练。示例代码使用PyTorch实现,详细解析了RMSprop的参数及其作用。适合初学者了解和实践。
25 1
|
10天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
16天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-SGD算法解析
SGD(随机梯度下降)是机器学习中常用的优化算法,特别适用于大数据集和在线学习。与批量梯度下降不同,SGD每次仅使用一个样本来更新模型参数,提高了训练效率。本文介绍了SGD的基本步骤、Python实现及PyTorch中的应用示例。
25 0
|
16天前
|
机器学习/深度学习 传感器 算法
Pytorch-Adam算法解析
肆十二在B站分享深度学习实战教程,本期讲解Adam优化算法。Adam结合了AdaGrad和RMSProp的优点,通过一阶和二阶矩估计,实现自适应学习率,适用于大规模数据和非稳态目标。PyTorch中使用`torch.optim.Adam`轻松配置优化器。
27 0
|
4天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
22天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
1天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。