力扣刷题 二叉树遍历的统一迭代法

题干

给定一个二叉树的根节点 root ,返回 它的 前中后序 遍历 。

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

上一次我们使用了迭代法来实现前中后序遍历,但是每一种遍历的访问和处理顺序不同,导致代码书写风格不同,不像是递归法,实现了其中的一种遍历方式,其他两种只要稍稍改一下节点顺序就可以了。

但其实针对三种遍历方式,使用迭代法是可以写出统一风格的代码的。下面我们就来实现一下。

我们以中序遍历为例,我们之前提到使用栈的话,无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)顺序不一致的情况。

事实上,访问这个操作是持续进行的,而处理节点则是需要时机的,在中序遍历中,时机就是遍历到叶子节点。关键是如何把处理节点和访问节点都用栈的逻辑解决,之前的迭代法中,用到了指针来帮助访问和处理。

我们将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。其实每一个节点都是需要处理的,只是时机未到,而做的标记则可以帮助我们判断处理节点的时机。

如何标记呢,就是将要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

添加左节点和右节点的时候,空节点不入栈,这样遇到空指针即代表遇到叶子节点,到了处理节点的时机。

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root != NULL) st.push(root);
        while(!st.empty()){
            TreeNode* node =st.top();
            //如果没有遇到标记,则访问
            if(node != NULL){
                //先弹出来,避免干扰了左中右的顺序
                st.pop();
                //如果右子树不是空节点,则入栈
                if(node->right) st.push(node->right);
                //将中节点入栈
                st.push(node);
                // 做标记,表示待处理
                st.push(NULL);
                //如果左子树不是空节点,则入栈 
                if(node->left) st.push(node->left);
            }
            //当遇到标记使,开始处理节点
            else{
                //把标记NULL弹出
                st.pop();
                //取出节点放入结果数组
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

而前序和后序遍历只需要改变访问的顺序即可

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);

                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

这样此时我们写出了统一风格的迭代法,不用在纠结于前序写出来了,中序写不出来的情况了。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python 之 Fastapi 框架学习

依赖安装 Fastapi 有版本要求&#xff0c;需要的 Python 版本至少是 Python 3.8&#xff08;不要犟&#xff0c;按照版本要求来&#xff0c;我最先也是在我 Python3.6 上装的&#xff0c;果不其然跑不起来&#xff09;&#xff0c;幸好我 Win7 老古董能支持的 Python 最高版本…

FastWiki发布`0.2.4`支持js 函数

Release v0.2.4 AIDotNet/fast-wiki (github.com) 支持JS动态functioncall调用支持动态function管理支持JS在线编辑提供智能代码提示支持JS在线编辑提供部分绑定的c#类&#xff08;默认提供Console&#xff0c;HttpClient&#xff09;支持Application绑定多个Function Call优…

跨站请求伪造漏洞(CSRF)

什么是CSRF CSRF&#xff08;Cross-Site Request Forgery&#xff09;&#xff0c;也被称为 one-click attack 或者 session riding&#xff0c;即跨站请求伪造攻击。 漏洞原理 跨站请求伪造漏洞的原理主要是利用了网站对用户请求的验证不严谨。攻击者会在恶意网站中构造一个…

linux 文件提权|属性修改

文章目录 suid&#xff08;set uid&#xff09;添加文件属性查看文件属性i &#xff08;immutable&#xff09; umask suid&#xff08;set uid&#xff09; 让文件在执行的时候具有属主&#xff08;对应文件 user &#xff09;的权限 chmod 7744 temp.txt 第一位的7表示权限位…

探寻大数据思想的主要贡献者与核心内容

引言&#xff1a; 在当今数字化时代&#xff0c;大数据已成为企业和科学研究的关键要素。其背后的思想和概念不仅引领了数据处理和分析的革新&#xff0c;也推动了人类对于信息时代的理解与认知。 大数据思想的起源&#xff1a; 在信息爆炸的时代背景下&#xff0c;大数据思…

海外仓的出入库流程有什么痛点?位像素海外仓系统怎么提高出入库效率?

随着跨境电商的蓬勃发展&#xff0c;海外仓是其中不可或缺的一个关键环节。而货物的出库与入库则是海外仓管理中的一个核心业务流程&#xff0c;它的运作效率直接影响到整个跨境物流的效率和客户体验。今天&#xff0c;让我们具体来看一看关于海外仓出入库的流程&#xff0c;其…

150行Python代码模拟太阳系行星运转

今天我们用Python来模拟一下太阳系行星运动轨迹~ 先上成品图&#xff08;运行效果含音乐的呦&#xff09; 想要实现这样的效果并不难 准备材料 首先我们需要准备这样一些材料 宇宙背景图 背景透明的行星图 编写代码 代码分块详解 导入需要的模块 import pygame import …

深度学习理论基础(六)多头注意力机制的自定义及Pytoch库的使用详细代码

目录 1. Scaled Dot-Product Attention2. 多头注意力机制框图&#xff08;1&#xff09;计算公式&#xff08;2&#xff09;具体计算过程&#xff08;3&#xff09;具体代码 深度学习中的注意力机制&#xff08;Attention Mechanism&#xff09;是一种模仿人类视觉和认知系统的…

轻量应用服务器4核8G12M配置优惠价格646元一年零3个月,12M公网带宽

腾讯云轻量4核8G12M服务器优惠价格646元15个月&#xff0c;买一年送3个月&#xff0c;配置为轻量4核8G12M、180GB SSD盘、2000GB月流量、12M带宽&#xff0c;腾讯云优惠活动页面 yunfuwuqiba.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云4核8G服务器租用价格 腾讯云&…

SaaS模式Java版云HIS系统源码 覆盖医院所有业务的HIS信息管理系统源码

SaaS模式Java版云HIS系统源码 覆盖医院所有业务的HIS信息管理系统源码 HIS&#xff08;Hospital Information System&#xff09;是覆盖医院所有业务和业务全过程的信息管理系统。 HIS系统以财务信息、病人信息和物资信息为主线&#xff0c;通过对信息的收集、存储、传递、统…

Android 窗口那些事儿

目录 1. &#x1f4c2; 前言 你&#xff0c;是否有过这些疑问&#xff1f; 2. &#x1f531; Window 2.1 认识 Window 的几个阶段 1&#xff09;阶段一&#xff1a;Window 约等于 Activity 2&#xff09;阶段二&#xff1a;Window 约等于 View 3&#xff09;阶段三&…

list的使用

前言 我们前面已经对string和vector进行了学习使用&#xff0c;以及对他们的底层进行了模拟实现&#xff01;本期我们继续学习STL的另外一个容器---list。 本期内容介绍 什么是list&#xff1f; list的常用接口 什么是list? 还是来看看官方的文档说明&#xff01; 这里通过…

[蓝桥杯 2017 国 C] 合根植物

[蓝桥杯 2017 国 C] 合根植物 题目描述 w 星球的一个种植园&#xff0c;被分成 m n m \times n mn 个小格子&#xff08;东西方向 m m m 行&#xff0c;南北方向 n n n 列&#xff09;。每个格子里种了一株合根植物。 这种植物有个特点&#xff0c;它的根可能会沿着南北…

【MySQL】增删改查操作(基础)

文章目录 1、新增操作&#xff08;Create&#xff09;1.1单行数据全列插入1.2多行数据指定列插入 2、查询操作&#xff08;Retrieve&#xff09;2.1全列查询2.2指定列查询2.3指定列查询2.4别名&#xff08;as&#xff09;2.5去重&#xff08;distinct&#xff09;2.6排序&#…

数据结构—图

图的基本概念 图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为&#xff1a;G(V,E)&#xff0c;其中&#xff0c;G 表示一个图&#xff0c;V 表示顶点的集合&#xff0c;E 表示边的集合。 顶点 图中的数据元素&#xff0c;我们称之为顶点&#xff0c;图至少有…

常见现代卷积神经网络(Pytorch 09)

本章将介绍现代的 卷积神经网络架构&#xff0c;许多现代卷积神经网络的研究都是建立在这一章的基础上的。在本章中的每一个模型都曾一度占据主导地位&#xff0c;其中许多模型都是 ImageNet竞赛 的优胜者。ImageNet竞赛自2010年以来&#xff0c;一直是计算机视觉中监督学习进展…

面试题——JVM老年代空间担保机制(我的想法)

这里借用一下人家的图&#xff0c;来说一下我的想法&#xff0c;嘻嘻。。。。 原文链接&#xff1a;一道面试题&#xff1a;JVM老年代空间担保机制-CSDN博客? 嗯&#xff0c;我觉得老年代担保机制的主要作用就是避免频繁触发FULL GC&#xff0c;这其实也是因为年轻代Minor GC…

Java项目:基于Springboot+vue社区医院管理系统设计与实现(源码+数据库+毕业论文)

一、项目简介 本项目是一套基于Springbootvue社区医院管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、功能…

数据结构之顺序表的相关知识点及应用

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 顺序表的概念及结构 顺序表的分类 顺序表的实现 在顺序表中增加数据 在顺序表中删除数据 在顺序表中查找数据 顺序表源码 顺序表的概念…

浮动辊位移测量功能块(CODESYS ST代码)

1、张力测量+标定(ST代码) 张力测量+标定(ST代码)_动态舞轮控制张力-CSDN博客文章浏览阅读804次。跳舞轮对应张力调节范围,我们可以通过改变气缸的气压方式间接改变,张力跳舞轮在收放卷闭环控制上的详细应用,可以参看下面的文章链接,这里我们主要讨论精密可调气阀的模拟量…