【刷力扣 TS 版】难度 简单,二叉树的前序遍历&后序遍历

简介: 【刷力扣 TS 版】难度 简单,二叉树的前序遍历&后序遍历

原文来自 我的个人博客

前言

拒绝摆烂ヾ(◍°∇°◍)ノ゙

从今天开始(2023/02/12),定一个小目标,先刷个 300Leetcode 题目(之前刷的不计入)。

当然作为一个小前端,我选择的语言是 TS,而且刷的题目的难度会偏中等一些,大概按照 简单3 中等6 困难1 这样的题型分布吧。嗯,目前是这么打算的。

本题 Github 地址:因为比较喜欢 vscode 的界面,而且方便调试,所以 AC 完就顺便提到 github 了,也算做一个记录吧。

本篇的题目是这个系列的第 NO.4NO.5 道,分别是 Leetcode 上第 144 道题 二叉树的前序遍历, 和第 145 道题 二叉树的后序遍历,难度都为 简单

我们开始吧,Here We Go~

1. 二叉树的前序遍历

1.1 题目描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入: root = [1,null,2,3]
输出: [1,2,3]

示例 2:

输入: root = []
输出: []

示例 3:

输入: root = [1]
输出: [1]

示例 4:

输入: root = [1,2]
输出: [1,2]

示例 5:

输入: root = [1,null,2]
输出: [1,2]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

1.2 解法一:递归

树的先序遍历的过程:

  1. 优先访问根节点
  2. 之后访问左子树
  3. 最后访问右子树

这种递归地方法是一种很容易理解的方法,只要在访问左右子树之前将当前节点的值 push 到最终的 ret 数组中即可。

function preorderTraversal(root: TreeNode | null): number[] {
  let ret: number[] = [];
  function traversal(root: TreeNode | null) {
    if(!root) return
    root.val !== null && ret.push(root.val);
    traversal(root.left);
    traversal(root.right);
  }
  traversal(root);

  return ret;
}

复杂度分析:

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)

1.3 解法二:迭代

我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同。

function preorderTraversal(root: TreeNode | null): number[] {
  let ret: number[] = [];

  if (!root) return [];
  let stack: TreeNode[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    if (node.val !== null) ret.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }

  return ret;
}

2. 二叉树的后序遍历

2.1 题目描述

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例 1:

输入: root = [1,null,2,3]
输出: [3,2,1]

示例 2:

输入: root = []
输出: []

示例 3:

输入: root = [1]
输出: [1]

提示:

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

2.2 解法一:递归

树的后序遍历的过程:

  1. 优先访问左子树
  2. 之后访问右子树
  3. 最后访问根节点

后续遍历递归的方法就是将遍历 root.val 的顺序放在了 遍历左节点遍历右节点 之后

function postorderTraversal(root: TreeNode | null): number[] {
  let ret: number[] = [];
  function traversal(root: TreeNode | null) {
    if(!root) return
    traversal(root.left);
    traversal(root.right);
    root.val !== null && ret.push(root.val);
  }
  traversal(root);

  return ret;
}

复杂度分析:

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)

2.3 解法二:迭代

同样,我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同。

function postorderTraversal(root: TreeNode | null): number[] {
  let ret: number[] = [];
  let stack: TreeNode[] = [];
  let current: TreeNode | null = root;
  let lastVisitedNode: TreeNode | null = null;
  while (stack.length || current !== null) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    current = stack[stack.length - 1];
    if (current.right === null || current.right === lastVisitedNode) {
      ret.push(current.val);
      lastVisitedNode = current;
      stack.pop();
      current = null;
    } else {
      current = current.right;
    }
  }

  return ret;
}

复杂度分析:

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)
相关文章
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
254 14
|
5月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
119 4
|
5月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
136 10
|
5月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
264 10
|
5月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
278 9
|
11月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
91 0
|
11月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
71 0
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
186 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
138 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
303 2

热门文章

最新文章