1. 二叉树介绍
在计算机科学中，二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。
二叉树是一种常见的数据结构，关于对二叉树的操作无外乎就是对它进行遍历。二叉树的遍历有前序、中序、后序、层序四种遍历方式，其中前三种也称为深度优先遍历，层序遍历也称为广度优先遍历。
2. 深度优先遍历
深度优先遍历通常有递归和迭代两种解法。以一个题为例：给定一个二叉树的根节点 root ，以数组的形式返回它的 前、中、后 遍历的结果。
前序遍历结果：[1, 2, 3]
中序遍历结果：[1, 3, 2]
后序遍历结果：[3, 2, 1]
2.1 递归解法
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
// 递归，时间O(n), 空间O(n)
const res: number[] = []
function visit(node: TreeNode): void{
res.push(node.val)
}
function dfs(node: TreeNode | null): void{
if(node === null) return
// 前序遍历写在这
visit(node)
dfs(node.left)
// 中序遍历写在这
// visit(node)
dfs(node.right)
// 后序遍历写在这
// visit(node)
}
dfs(root)
return res
}
对于前序、中序和后序遍历，只需将递归函数里的 visit 函数放在不同位置即可，其他的代码完全一样。
2.2 迭代解法
2.2.1 前序遍历
function preorderTraversal(root: TreeNode | null): number[] {
// 迭代
function visit(node: TreeNode): void{
res.push(node.val)
}
const res: number[] = []
// 初始化栈
const stack: TreeNode[] = []
// cur是遍历指针
var cur: TreeNode = root
while(cur !== null || stack.length !== 0){
while(cur !== null){
// 将根节点 cur 和所有的左孩子入栈并加入结果中，直至 cur 为空
visit(cur)
stack.push(cur)
cur = cur.left
}
// 每弹出一个栈顶元素 temp，就到达它的右孩子
var temp: TreeNode = stack.pop()
cur = temp.right
}
return res
}
2.2.2 中序遍历
和前序遍历的代码完全相同，只是在出栈的时候才将节点 temp 的值加入到结果中。
function inorderTraversal(root: TreeNode | null): number[] {
function visit(node: TreeNode): void{
res.push(node.val)
}
const res: number[] = []
const stack: TreeNode[] = []
var cur: TreeNode = root
while(cur !== null || stack.length !== 0){
while(cur !== null){
stack.push(cur)
cur = cur.left
}
var temp: TreeNode = stack.pop()
visit(temp)
cur = temp.right
}
return res
}
2.2.3 后序遍历
继续按照上面的思想，这次我们反着思考，节点 cur 先到达最右端的叶子节点并将路径上的节点入栈；然后每次从栈中弹出一个元素后，cur 到达它的左孩子，并将左孩子看作 cur 继续执行上面的步骤。最后将结果反向输出即可。
function postorderTraversal(root: TreeNode | null): number[] {
function visit(node: TreeNode): void{
res.push(node.val)
}
const res: number[] = []
const stack: TreeNode[] = []
var cur: TreeNode = root
while(cur !== null || stack.length !== 0){
while(cur !== null){
// 先到达最右端
visit(cur)
stack.push(cur)
cur = cur.right
}
// 每弹出一个栈顶元素 temp，就到达它的左孩子
var temp: TreeNode = stack.pop()
cur = temp.right
}
return res.reverse() // 反向输出
}
3. 广度优先遍历
二叉树的广度优先遍历一般采用迭代方法，与前面深度优先遍历的迭代方法实现有所不同。前面的迭代方法都使用栈实现，而广度优先遍历使用队列实现。以一个题为例：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：
返回其层序遍历结果：[ [3], [9,20], [15,7] ]
广度优先遍历的步骤为：
- 初始化队列 q，并将根节点 root 加入到队列中；
- 当队列不为空时：
队列中弹出节点 node，加入到结果中；
如果左子树非空，左子树加入队列；
如果右子树非空，右子树加入队列；
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
if (root == null) {
return []
}
let result: number[][] = []
let queue: TreeNode[] = [root]
while (queue.length) {
// 每一层的节点数
let level: number = queue.length
let currLevel: number[] = []
// 每次遍历一层元素
for (let i = 0; i < level; i++) {
// 当前访问的节点出队
let curr: TreeNode = queue.shift()
// 出队节点的子女入队
if (curr.left) queue.push(curr.left)
if (curr.right) queue.push(curr.right)
currLevel.push(curr.val)
}
result.push(currLevel)
}
return result
};
