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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
云解析DNS,个人版 1个月
简介: ☆打卡算法☆LeetCode 144. 二叉树的前序遍历 算法解析

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

一、题目

1、算法题目

“给定二叉树的根节点,返回节点值的前序遍历。”

2、题目描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

1702361142015.jpg

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

二、解题

1、思路分析

二叉树的前序遍历已经说过很多遍了。

也就是从根节点出发,按照左子树→右子树的顺序遍历整个树。

在访问的时候也是左子树→右子树的顺序访问。

按照这种方式遍历整个树,整个遍历的方式就具有递归的性质。

2、代码实现

代码参考:

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

1702361170067.jpg

3、时间复杂度

时间复杂度:O(n)

其中n是二叉树的节点数,每个节点整个被遍历一次。

空间复杂度:O(n)

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

三、总结

首先将根节点的值存入答案

然后递归调用函数,将左子树传递进去,最后递归调用函数,将右子树传递进去。

以前序遍历的方式遍历整棵树,递归终止条件是碰到空节点。

相关文章
|
7天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
17 3
|
11天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
181 1
|
1天前
|
机器学习/深度学习 存储 数据采集
强化学习系列:A3C算法解析
【7月更文挑战第13天】A3C算法作为一种高效且广泛应用的强化学习算法,通过结合Actor-Critic结构和异步训练的思想,实现了在复杂环境下的高效学习和优化策略的能力。其并行化的训练方式和优势函数的引入,使得A3C算法在解决大规模连续动作空间和高维状态空间的问题上表现优异。未来,随着技术的不断发展,A3C算法有望在更多领域发挥重要作用,推动强化学习技术的进一步发展。
|
10天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
15天前
|
安全 算法 Java
密码学基础知识与加密算法解析
密码学基础知识与加密算法解析
|
17天前
|
存储 算法 搜索推荐
力扣每日一题 6/13 反悔贪心算法
力扣每日一题 6/13 反悔贪心算法
10 1
|
17天前
|
存储 算法 安全
深入解析消息认证码(MAC)算法:HmacMD5与HmacSHA1
深入解析消息认证码(MAC)算法:HmacMD5与HmacSHA1
|
9天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
13天前
|
机器学习/深度学习 人工智能 算法
计算机算法基础概述与常用算法解析
计算机算法基础概述与常用算法解析
|
13天前
|
安全 算法 Java
密码学基础知识与加密算法解析
密码学基础知识与加密算法解析