1. 首页
  2. LeetCode 刷题网

LeetCode 145. 二叉树的后序遍历

题目描述

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

难度:Middle

前置知识

  • 递归

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

相比于前序遍历,后续遍历思维上难度要大些,前序遍历是通过一个stack,首先压入父亲结点,然后弹出父亲结点,并输出它的value,之后压人其右儿子,左儿子即可。

然而后序遍历结点的访问顺序是:左儿子 -> 右儿子 -> 自己。那么一个结点需要两种情况下才能够输出:
第一,它已经是叶子结点;
第二,它不是叶子结点,但是它的儿子已经输出过。

那么基于此我们只需要记录一下当前输出的结点即可。对于一个新的结点,如果它不是叶子结点,儿子也没有访问,那么就需要将它的右儿子,左儿子压入。
如果它满足输出条件,则输出它,并记录下当前输出结点。输出在stack为空时结束。

关键点解析

  • 二叉树的基本操作(遍历)
    > 不同的遍历算法差异还是蛮大的
  • 如果非递归的话利用栈来简化操作

  • 如果数据规模不大的话,建议使用递归

  • 递归的问题需要注意两点,一个是终止条件,一个如何缩小规模

  1. 终止条件,自然是当前这个元素是null(链表也是一样)

  2. 由于二叉树本身就是一个递归结构, 每次处理一个子树其实就是缩小了规模,
    难点在于如何合并结果,这里的合并结果其实就是left.concat(right).concat(mid),
    mid是一个具体的节点,left和right递归求出即可

代码

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  // 1. Recursive solution

  // if (!root) return [];

  // return postorderTraversal(root.left).concat(postorderTraversal(root.right)).concat(root.val);

  // 2. iterative solutuon

  if (!root) return [];
  const ret = [];
  const stack = [root];
  let p = root; // 标识元素,用来判断节点是否应该出栈

  while (stack.length > 0) {
    const top = stack[stack.length - 1];
    if (
      top.left === p ||
      top.right === p || // 子节点已经遍历过了
      (top.left === null && top.right === null) // 叶子元素
    ) {
      p = stack.pop();
      ret.push(p.val);
    } else {
      if (top.right) {
        stack.push(top.right);
      }
      if (top.left) {
        stack.push(top.left);
      }
    }
  }

  return ret;
};

复杂度分析

  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

相关专题

更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 145. 二叉树的后序遍历

链接:https://www.javascriptc.com/4509.html

« LeetCode 146. LRU缓存机制
2020七夕又来了,教你给女朋友做个动态二维码»
Flutter 中文教程资源

相关推荐

QR code