二叉树刷题记(四-前序遍历)

简介: 二叉树刷题记(四-前序遍历)

前言

  • 大家好呀!小嘟又和大家见面了,今天为大家带来的是二叉树前序遍历。
  • 题号为

看完本篇文章你会发现这道题竟然这么简单。


代码都是小嘟在力扣上测试过的,没有问题哒!


本篇是写的关于二叉树的前序遍历递归和迭代代码。若想学习另外两种遍历方法,请滑到文章底部,小嘟准备了直通车哦


下一篇文章小嘟准备说说它们代码之间的异同在哪里.


本文目的


掌握二叉树的前序遍历过程

掌握前序遍历的递归和迭代代码

读者能够独立的完成力扣上序号为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啦!!!,溜啦溜啦...

相关文章
|
1月前
|
存储 索引
手撸二叉树——二叉查找树
二叉树是数据结构中非常重要的一种数据结构,它是树的一种。
12 2
|
1月前
|
Java
手撸二叉树——AVL平衡二叉树
本文介绍了AVL平衡二叉树的基本概念和实现方法。首先回顾了二叉查找树在插入节点后的不平衡问题,然后详细讲解了四种旋转操作:左左单旋转、右右单旋转、左右双旋转和右左双旋转,以确保树的平衡。文章还提供了Java代码实现,包括节点插入、删除和平衡调整的具体方法。通过这些操作,AVL树能够保持较低的高度,从而提高查询性能。
26 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
6月前
二叉树刷题记(二-中序遍历)
二叉树刷题记(二-中序遍历)
|
6月前
|
算法
二叉树刷题记(三-后序遍历)
二叉树刷题记(三-后序遍历)
|
6月前
二叉树刷题记(七-二叉树的右侧视图)
二叉树刷题记(七-二叉树的右侧视图)
|
6月前
|
算法
二叉树刷题记(六-二叉搜索树的第k大节点)
二叉树刷题记(六-二叉搜索树的第k大节点)
|
6月前
|
算法
二叉树刷题记(八-二叉树的最大深度-深度遍历)
二叉树刷题记(八-二叉树的最大深度-深度遍历)
|
Cloud Native
【刷题日记】590. N 叉树的后序遍历
本次刷题日记的第 5 篇,力扣题为:【刷题日记】590. N 叉树的后序遍历 ,简单
|
Cloud Native
【刷题日记】589. N 叉树的前序遍历
本次刷题日记的第 4 篇,力扣题为:589. N 叉树的前序遍历 ,简单