二叉树前序遍历详解[通俗易懂]

二叉树前序遍历详解[通俗易懂]二叉树的遍历是数据结构中非常基础的内容了,今天这一篇文章我们来详细了解一下二叉树的前序遍历,二叉树的前序遍历顺序是根节点-左子树-右子树,本文对递归和栈模拟的方法都有实现一、递归方法递归方法可以说是很简了,我们秉承先去往左节点再去往右节点的原则就好了//assumethatwehaveTreeNode,andresistostoretheanswervoidpreorder(TreeNode*root,vector<int&.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

二叉树的遍历是数据结构中非常基础的内容了,今天这一篇文章我们来详细了解一下二叉树的前序遍历,二叉树的前序遍历顺序是根节点-左子树-右子树,本文对递归和栈模拟的方法都有实现

一、递归方法

递归方法可以说是很简了,我们秉承先去往左节点再去往右节点的原则就好了

// assume that we have TreeNode, and res is to store the answer 
        
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val); // we will record every node we have traveled
        preorder(root->left, res); // to left first
        preorder(root->right, res); // to right
    }
    

    //main
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }

二、栈实现

我们使用栈迭代来模拟递归的过程,事实上,递归的过程隐式地维护了一个栈,(递归储存了状态,当return 的时候相当于状态集合的.pop() )

具体地:我们将我们从根节点开始遍历到的每一个值都放入我们的答案数组,将遇到的每一个节点都放入节点数组,当节点往一个方向遍历到底(node == NULL) 的时候,我们就要pop这个栈,回到上一层,就像递归的 return 一样

记住:遍历完左边再往右边走,这也是代码中第二个while 的意义

vector<int> preorderTravel (TreeNode root) {
	vector<int> res ; // store the answer
	
	if(root == NULL) {
		return ans ;
	}
	
	stack<TreeNode*> stk ; // store every node we have traveled
	TreeNode *node = root ;
	while(!stk.empty() || node != NULL) {
		while(node != NULL) {
			res.emplace_back(node -> val) ; // push_back,we should every val we met in "preorderTravel"
			stk.emplace(node) ; // push
			node = node -> left ; // go to left frst
		}
		
		node = stk.top() ; 
		stk.pop() ; // same as "return" in recursion
		node = node -> right ;
	}
	
	return res ;
}

本文主要是对栈模拟实现递归的一个练习,如有不正,请指出,感激不尽

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195293.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 阶乘的累加和

    阶乘的累加和

  • ping原理和Traceroute原理

    ping原理和Traceroute原理ping原理ping主要是用来探测主机和主机之间是否可以进行通信,如果不能ping到某台主机,表示不能与这台主机建立连接。ping使用的是ICMP协议,他发送ICMP回送请求消息给目的主机。ICMP协议规定:目的主机必须返回ICMP回送应答消息给源主机,如果源主机在一定时间内收到应答,表明主机可达。ICMP协议是通过IP协议发送的,IP协议是无连接的,不可靠的数据报协议。ping是用来检测…

  • CString和char*转换的理解

    CString和char*转换的理解

  • hsql是什么_MQL语言

    hsql是什么_MQL语言Hsqldb是一个开放源代码的JAVA数据库,其具有标准的SQL语法和JAVA接口,它可以自由使用和分发,非常简洁和快速的。AD:51CTO学院:IT精品课程在线看!Hsqldb是一个开放源代码的JAVA数据库,其具有标准的SQL语法和JAVA接口,它可以自由使用和分发,非常简洁和快速的。具有Server模式,进程内模式(In-Process)和内存模式(M

  • python中多个if语句用法_python中if函数多个条件怎么用

    python中多个if语句用法_python中if函数多个条件怎么用python的if语句为条件判断语句,习惯与else搭配使用。if结构允许程序做出选择,并根据不同的情况执行不同的操作if的用法1.只有if进行判断desserts=[‘icecream’,’chocolate’,’applecrisp’,’cookies’]favorite_dessert=’applecrisp’hate_dessert=’chocolate’fo…

  • 2018年又传喜报!热烈祝贺王家林大师大数据经典著作《Spark SQL大数据实例开发教程》 畅销书籍 出版上市![通俗易懂]

    2018年又传喜报!热烈祝贺王家林大师大数据经典著作《Spark SQL大数据实例开发教程》 畅销书籍 出版上市![通俗易懂]2018年又传喜报!热烈祝贺王家林大师大数据经典著作《SparkSQL大数据实例开发教程》畅销书籍出版上市!作者:王家林段智华 条码书号:9787111591979出版日期:2018/3/1出版社:机械工业出版社丛书名:大数据科学丛书定价:¥59.00        SparkSQL是Spark生态环境中核心和基础的组件,是掌握Spark的关键所在。本书完全从企业级开发的角度出…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号