原文来自 我的个人博客
前言
拒绝摆烂ヾ(◍°∇°◍)ﾉﾞ
从今天开始（2023/02/12），定一个小目标，先刷个 300 道 Leetcode 题目（之前刷的不计入）。
当然作为一个小前端，我选择的语言是 TS，而且刷的题目的难度会偏中等一些，大概按照 简单3 中等6 困难1 这样的题型分布吧。嗯，目前是这么打算的。
本题 Github 地址：因为比较喜欢 vscode 的界面，而且方便调试，所以 AC 完就顺便提到 github 了，也算做一个记录吧。
本篇的题目是这个系列的第 NO.4 和 NO.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 解法一：递归
树的先序遍历的过程：
- 优先访问根节点
- 之后访问左子树
- 最后访问右子树
这种递归地方法是一种很容易理解的方法，只要在访问左右子树之前将当前节点的值 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 解法一：递归
树的后序遍历的过程：
- 优先访问左子树
- 之后访问右子树
- 最后访问根节点
后续遍历递归的方法就是将遍历 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)。
