前言
- 大家好呀!小嘟又和大家见面了,今天为大家带来的是二叉树前序遍历。
- 题号为
看完本篇文章你会发现这道题竟然这么简单。
代码都是小嘟在力扣上测试过的,没有问题哒!
本篇是写的关于二叉树的前序遍历递归和迭代代码。若想学习另外两种遍历方法,请滑到文章底部,小嘟准备了直通车哦
下一篇文章小嘟准备说说它们代码之间的异同在哪里.
本文目的
掌握二叉树的前序遍历过程
掌握前序遍历的递归和迭代代码
读者能够独立的完成力扣上序号为144的题目
虽然小嘟爱叨叨,但不能再说了,该上干货啦!!!
- 正文
- 预备知识1:
- 二叉树
前序遍历
的顺序是什么呢? 小嘟说
:父结点-》左孩子-》右孩子- 上例子
上图的顺序为[1,2,4,5,3,6]
可以这样理解:假如这是6个景点,小嘟现在要去旅游,我先到1位置,然后到2位置…,我每到一个地方我要拍照记录,然后我才去下一个地方。前序遍历就可以这样理解,你把小嘟拍照的事情改成打印1,打印2…,这样理解应该好理解一点了。若觉得文章有任何问题,欢迎在评论区指出,谢谢。
- 1.题目如下
- 2.代码实现
思想
:在二
- 叉树前序遍历中,根节点是第一个访问的,就类似于小嘟旅游的第一个景点,之后就找左孩子,如果左孩子有,那就一直找左孩子的左孩子…,直到当前结点的左孩子为null,那么就去找当前结点的右孩子…
- 思想不难,二叉树的前序遍历应该算是这三种遍历中最简单,最容易懂的。
- 话不多说上
迭代代码
var preorderTraversal = function(root) { let res = [];//最后返回的数组,存储的是遍历的序列 let stack = [];//循环过程中遇到的结点信息 while(root || stack.length){ //key1 while(root){ res.push(root.val); //将遇到的打印,这里是存储哦 stack.push(root); // 这里你可以理解成,该结点还要记着怎样找到 // 自己的右孩子。 root = root.left; //找左孩子 } //key2 let node = stack.pop(); //找不到左孩子了,那就要找该结点的右孩子啦 root = node.right; //找右孩子 } return res; };
解释
用上边小嘟举的二叉树例子走一遍
看着代码,我来说下过程,循环进来,先进入key1处,然后将1入res数组,将值为1的结点信息保存在stack数组中,依次将2入res数组,将值为2的结点信息保存在stack数组中,然后到了值为4的结点,将它进行上述操作后,root = root.left,此时,root为null,循环退出啦,我们要开始执行key2处的代码啦。当前stack数组的最后一个元素保存的是值为4的结点,弹出该结点(弹出的意思就是删除并返回),然后找该结点的右孩子(因为在key1这个循环里已经将该结点的左孩子找过啦,左孩子为null),之后的读者可以自己画画,可以加深印象。
res数组中的元素变化过程:
- [1]
- [1,2]
- [1,2,4]
- [1,2,4,5]
- [1,2,4,5,3]
- [1,2,4,5,3,6]
递归代码
,这个小嘟觉得自己写的已经很详细啦,直接看呗(嘿嘿嘿
)
var preorderTraversal = function(root) { let res = [];//最后返回的数组,存储的是遍历的序列 //这里用到了es6中的箭头函数 const traversal = (root01)=>{ //如果当前结点为null, if(root01 == null) return ;//说明这条路径走到尽头了,需要重新找路 res.push(root01.val); //将遇到的打印,这里是存储哦 traversal(root01.left); //找左孩子 traversal(root01.right); //找右孩子 } traversal(root); return res;//返回值 };
结尾
到今天为止,二叉树的三种遍历方法就结束啦,小嘟自认为讲的很清楚,因为小嘟自己都清楚啦。
下篇文章想分析下它们三者代码的异同。
小嘟笔拙,有不对的地方,欢迎指出,谢谢!!!
最后希望看完这几篇文章的读者,能够写出这三种方法,面试的时候在再不慌啦!
要是还能点那个赞,关注一波,那就更nice啦!!!,溜啦溜啦...