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

发表于

这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战

前言

  • 昨天做了一道二叉树的中序遍历题目， 采用递归方式完成，今天更新第二种方法，使用迭代方法完成本题。在面试的时候，面试让你手写非递归的代码可能性会大一点，因为递归就那么几行代码，看一眼就会了。
  • 什么是迭代呢？
+ 在我的认识里：迭代就是使用**循环嵌套**的方式，然后借助辅助空间，例如数组等其他数据结构。
  • 越是比较难写出来的代码，它的质量一般来说是比较高的
  • 本文目的
+ 1.二叉树的中序遍历过程
+ 2.学会中序遍历的非递归代码，理解并掌握代码的实现过程
+ 3.希望本文章对你学习写代码有一定的帮助
**正文**
  • 预备知识1：
+ 二叉树中**左孩子**、**右孩子**、**父结点**代表的是什么？

image.png

  • 预备知识2：
+ **中序遍历**的顺序是什么呢？
+ 左孩子-》父结点-》右孩子
+ 上图的输出顺序为 [4,2,5,1,3,6]
+ 这个应该很好计算出来的，如果不会，欢迎下方评论区留言，我会专门讲解一下，也就当是给自己复习咯！
  • 啦啦啦，差不多了。当然你还得掌握循环和数组这些基本知识
  • 1.题目如下
    image.png
  • 2.代码实现
+ **代码思想**：首先，我们得用一个栈来保存我们在循环过程中遇到的元素，遇到就把元素压栈。那么这里又有一个问题，我们不能只入栈而不出栈，**那我们什么时候出栈呢？**
+ 我们知道，中序遍历是从左孩子开始的，所以我们应该是左孩子为null，也就是没有左孩子的时候出栈(这只是我的一种解释，不同人对这个解释不一样)，知道这个这个问题就差不多了。
+ 树这个数据结构，遇到该类型问题我的理解就是将问题转化成一个结点的问题，这个结点能处理好了，那么其他的也就大致差不多，而且我觉得树的问题有一定的规律可循，这个还是需要慢慢发现的。
+ 直接看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ini复制代码var inorderTraversal = function(root) {
   let res  = [];//最后要返回的数组
   let stack = [];//我们用来存储遍历过程中遇到的元素
   //root == null 并且 stack.length == 0(循环退出)    
   while(root||stack.length){
        while(root){//当前元素存在就循环
           stack.push(root);//把当前元素入栈，不是入的值，而是当前的整个元素
           root = root.left;//继续找它的左孩子
        }
        //该元素没有左孩子，那么我们就应该打印该元素
        let target  = stack.pop();//返回该元素并出栈
        res.push(target.val);//将该元素的值压入要返回的栈里边
        root = target.right;//遍历该元素的右孩子，因为左边和中间（父结点）已经遍历过了
   }
   return res;//返回最终的结果
};
  • 解释
+ 外层循环的判断条件（root||stack.length)
+ 循环退出的条件
+ root == null **并且** stack.length == 0
+ root == null的意思就是继续以该方向往下找已经找不到了，需要退回另走一个方向试试
+ stack.length == 0就是所有元素已经遇见并且都打印了
+ **注**：这里说的是root刚开始不是null它的过程
+ 其他的重点我都写在代码那里了，若有那一部分解释有问题，欢迎提出。
**结尾**
  • 本人笔拙，有的地方写的可能不对，欢迎提出。
  • 希望文章对你有所帮助，若觉得还有点用，欢迎点赞支持。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%