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

发表于

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

前言

  • 今天做了关于二叉树的后序遍历题目，我的计划是先将二叉树的前中后三种遍历算法掌握，然后再做关于二叉树的其他题目。
  • 今天不将递归和迭代代码分开啦！一起讲了。
  • 我最近的感悟：题目看不懂，那就直接去看题解，题解还看不懂，那就直接看代码，然后带一个例子把程序走一遍，最后在翻过头来看题解，我想看不太懂也差不多了。
  • 重点：看懂之后记得多敲几遍，最好形成条件反射，一看到这个题就知道代码是什么了。
  • 目标：不求所有的都会，我们也做不到，只求我们做过的你还能做出来就足够了。
  • 本文目的
+ 掌握二叉树的后序遍历过程。
+ 掌握后序遍历的递归和迭代代码。
+ 希望亲爱的读者，看完本文章，能掌握这两种算法。
**正文**
  • 预备知识1：
+ 默认读者已了解二叉树的基本概念。
  • 预备知识2：
+ **后序遍历**的顺序是什么呢？
+ 左孩子-》右孩子-》父结点
+ 上例子
![image.png](https://gitee.com/songjianzaina/juejin_p11/raw/master/img/44c2f2c85ba4294bc5d956314af77f4939262d19c60cabbc3e6f385b194f590e)
+ 上图的顺序为[4,5,2,6,3,1]
+ 读者有任何问题，欢迎下方留言，我们一起学习喽！
  • 1.题目如下
    image.png
  • 2.代码实现
+ **思想**：后序遍历中各父结点是最后一个访问，根节点是所有元素访问完之后才会访问。
+ **迭代代码**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ini复制代码var postorderTraversal = function(root) {
   let res = [];//最后要返回的数组
   let stack = [];//遍历过程中遇到的元素结点
   while(root || stack.length){
       while(root){
           res.unshift(root.val);//这个是数组的一个方法，可以理解成头插法，往首部插入
           stack.push(root);
           root = root.right;
       }
       let node  = stack.pop();
       root = node.left;
   }
   return res;
};
  • 解释
+ 这个代码是先找父结点，然后一直找的是**父结点的右孩子**，不知道读者看出来了吗？
+ 每遇到一个结点，就用**头插法**，把该结点的val值插入到返回的数组中。这个过程，就是算法的核心，这个地方理解了，那么这个代码也就通了。我先和读者**一起走一遍**，起初，我们先判断root是否为null，若是null，那么不进入循环，直接return；反之，将根节点的val头插法到res数组中，将根节点整体入stack数组中，然后找它的右孩子，如果有的话，继续循环，这个地方，我们可以知道，每循环一次，总是将一个结点的val插入到到res数组的第一个位置中。
+ 总结 :**根元素的val值被放到了res数组的最后一个**，我们**找的顺序**是父结点-》右孩子-》左孩子，**输出顺序**就是左孩子-》右孩子-》父结点喽！(因为我们是用的**头插法**)
+ 这里我们**上边的图**再来说一遍。请读者耐住性子，相信我，看完不懂你捶我。
+ res数组中的**元素变化**过程


    - [1]
    - [3,1]
    - [6,3,1]
    - [2,6,3,1]
    - [5,2,6,3,1]
    - [4,5,2,6,3,1]
    - 这不就是我们想要的的后序遍历顺序吗？
    - 结束啦，有任何问题欢迎下方留言。
+ **递归代码**
1
2
3
4
5
6
7
8
9
10
11
scss复制代码var postorderTraversal = function(root) {
  let res = [];//要返回的数组
  const traversal = (root01)=>{
      if(root01 == null) return;//找到尽头，需要另换路
      traversal(root01.left);//遍历左子树
      traversal(root01.right);//遍历右子树
      res.push(root01.val);//左右子树遍历结束就只剩中间喽！
  }
  traversal(root);
  return res;
};
+ 递归有问题的，小嘟建议你做题的时候可以画下图，边看代码边画图，不一会你就懂啦。
**结尾**
  • 下如果你认真看完本文章，我相信你肯定会的。
  • 下次出一篇前序遍历的迭代和递归代码，然后看能不能找出它们之间的共性。
  • 本人笔拙，有的地方写的不对，欢迎指出，谢谢！！！
  • 最后，祝大家看完该文章有所收获，我们下期再见。

本文转载自: 掘金

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

0%