前言
- 大家好呀！小嘟又和大家见面了，今天为大家带来的是二叉树前序遍历。
- 题号为
看完本篇文章你会发现这道题竟然这么简单。
代码都是小嘟在力扣上测试过的，没有问题哒！
本篇是写的关于二叉树的前序遍历递归和迭代代码。若想学习另外两种遍历方法，请滑到文章底部，小嘟准备了直通车哦
下一篇文章小嘟准备说说它们代码之间的异同在哪里.
本文目的
掌握二叉树的前序遍历过程
掌握前序遍历的递归和迭代代码
读者能够独立的完成力扣上序号为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啦！！！，溜啦溜啦...
