二叉树刷题记（四-前序遍历）

前言

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

• 题号为
  

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

• 代码都是小嘟在力扣上测试过的，没有问题哒！

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

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

• 本文目的

  • 掌握二叉树的前序遍历过程
  • 掌握前序遍历的递归和迭代代码
  • 读者能够独立的完成力扣上序号为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的结点，d出该结点（d出的意思就是删除并返回），然后找该结点的右孩子（因为在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啦！！！，溜啦溜啦...

附件

• 二叉树中序遍历

  • 递归版 https://juejin.cn/post/7027482621089153038
  • 迭代版 https://juejin.cn/post/7027747932711419935

• 二叉树后序遍历
  https://juejin.cn/post/7029113350264979493