二叉树的前序遍历--非递归解法(简单难度)_二叉树栈非递归遍历思想算法难吗-程序员宅基地

技术标签: 数据结构专栏---二叉树  java  二叉树  leetcode  数据结构  

题目概述(简单难度)

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

在这里插入图片描述

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

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:
在这里插入图片描述

输入:root = [1,2]
输出:[1,2]

示例 5:
在这里插入图片描述

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

题目链接
点我进入leetcode

思路与代码

思路展现

这道题目的思路我放到了这篇博客里,大家点击对应目录便可以查看啦:
点我进入博客

代码示例

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
    
       List<Integer> list = new ArrayList<>();
       if (root == null) {
    
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
    
            while (cur != null) {
    
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
}

时间复杂度:O(N)
空间复杂度:O(N)

总结

非递归解法是比较难的一个解法,比递归解法繁琐,逻辑没有递归那么清晰,但是也是不错的一个解法,希望大家好好学习

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41972686/article/details/120852998

智能推荐

CheckableLinearLayout 实现一个可选中的layout 以及 CheckableImageView_linearlayout setchecked-程序员宅基地

文章浏览阅读2.3k次。package com.example.testchecklinearlayout;import android.content.Context;import android.util.AttributeSet;import android.widget.Checkable;import android.widget.LinearLayout;public class Checkab_linearlayout setchecked

git---全局设置用户名、密码、邮箱_git global username-程序员宅基地

文章浏览阅读1w次,点赞4次,收藏16次。git—全局设置用户名、密码、邮箱git config命令的–global参数,用了这个参数,表示你这台机器上所有的Git仓库都会使用这个配置,当然也可以对某个仓库指定不同的用户名和Email地址。1.查看git配置信息$ git config --list2.查看git用户名、密码、邮箱的配置$ git config user.name$ git config user.password$ git config user.email3.设置git用户名、密码、邮箱的配置$ git con_git global username

WakeOnLan+RemoteDesktop_wake on lan and remote desktop-程序员宅基地

文章浏览阅读713次。这两天就要开学了,之前的几个学期我都是把台式机搬到学校去但是这学期格外的懒,于是就想到了利用网络唤醒加上远程桌面远程访问家里的台式机WakeOnLan查看主板是否支持wol(只要不是太老的主板都支持)进入BIOS,开启wol 这个选项的主板不一样叫法不同,根据主板类型上网查一下就好,我的主板是b75,选项叫PME唤醒进入系统,打开设备管理器,选择你的网卡,点击属性最后一栏,至少勾选前两项.然后将..._wake on lan and remote desktop

Mac OS X 10.4作为客户端挂载SMB时显示0字节可用问题解决-程序员宅基地

文章浏览阅读531次。最近遇到一件怪事,RHEL运行的samba,用Mac OS X 10.4去访问,无论怎样都显示可用空间为0字节,可以创建目录,无法写入文件。文件服务器实际上有nTB可用。为解决问题,google上搜了搜,下面是两个相关的讨论:http://discussions.apple.com/thread.jspa?messageID=5540225http://discussion..._smb共享全部0字节

-XX:+TraceClassLoading参数可以跟踪显示类加载机制-程序员宅基地

文章浏览阅读3.8k次。-XX:+TraceClassLoading_-xx:+traceclassloading

B&O蓝牙耳机E8的连接_bo e8蓝牙连接-程序员宅基地

文章浏览阅读10w+次。 1、从充电盒中取出耳机,然后点击右耳机将其打开。产品指示灯变为白色,可听到声音,这时产品就可以使用了。2、使耳机之间保持小于20cm的距离,触摸并按住2只耳机5秒钟以启动蓝牙配对。指示灯开始闪烁蓝色,并听到声音提示。打开设备上的蓝牙设置,然后选择 Beoplay E83、按键操作如下:播放/暂停 右耳机按1下 下一曲 右耳机按2下 上一曲 ..._bo e8蓝牙连接

随便推点

WinDbg命令详解--进程_windbg 调试怎么查看进程-程序员宅基地

文章浏览阅读2.4k次。指令列表.tlist 查看进程简要信息:进程号和进程名称.tlist 查看进程详细信息:进程号和进程名称,命令行参数,SessionID,用户等信息!teb 线程块环境信息!peb 进程块环境信息lm 查看模块的简要信息lm -v 查看模块的相信信息!handle 查看句柄表信息!handle id 查看特定的句柄信息_windbg 调试怎么查看进程

0x8(0x80070035找不到网络路径)-程序员宅基地

文章浏览阅读242次。c语言编程 main()  {unsignedchara,b,ca为16进制化为二进制为0011,b为0011|1000=1011=11,c为b左移一位为10110相当于b*2=22请教大家一个计算机2级的题目main(){unsignedcha"|"这个是按位或C没有初始化不能移位操作,安装程序..._找不到网络名称0x8

两个暴牛的js加密函数 求解码办法-程序员宅基地

文章浏览阅读630次。eval(function(p,a,c,k,e,d){e=function(c){return(c<a?"":e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--)d[e(c)]=k[c]||e(c);k=[...

基于Python爬虫黑龙江哈尔滨天气预报数据可视化系统设计与实现(Django框架) 研究背景与意义、国内外研究现状-程序员宅基地

文章浏览阅读2.5k次,点赞15次,收藏24次。基于Python爬虫黑龙江哈尔滨天气预报数据可视化系统设计与实现(Django框架) 研究背景与意义、国内外研究现状,帮助用户更好地理解和利用天气数据。而基于Python爬虫的天气预报数据可视化系统,能够利用Python强大的数据分析和可视化库,提供更加灵活、自定义的天气预报数据查询和展示功能。另外,一些研究者也将天气数据与其他数据进行融合,实现多维度的可视化分析,如将天气数据与交通数据结合,帮助用户了解天气对交通流量的影响。同时,这些网站通常有着繁琐的页面布局和冗长的加载时间,用户体验较差。

Windows操作系统下IIS版本对应关系_2003 iis7.5-程序员宅基地

文章浏览阅读6.9k次。各个系统对应的iis版本不同:Windows 2000 Server→IIS5.0Windows XP SP1→IIS5.0 Windows XP SP2,SP3→IIS5.1 Windows Server 2003→IIS6.0Windows Vista Ultimate→IIS7.0Windows 7→iis7, iis7.5Windows server2008_2003 iis7.5

[linux-016] 用gparted修复优盘或者移动硬盘_gparted如何修复-程序员宅基地

文章浏览阅读912次。gparted,可以修复数据,可以新建分区表。apt-get install gpartedroot权限,启动gparted。_gparted如何修复

推荐文章

热门文章

相关标签