1. 二叉树的构建
本文的二叉树默认指的是二叉搜索树BST，二叉搜索树有如下特点
- 一个节点如果有左孩子，那么左孩子的值小于该节点
- 一个节点如果有右孩子，那么右孩子的值大于该节点
在此基础上我们进行二叉树的构建，首先定义节点类TreeNode
export class TreeNode {
constructor(val, left, right) {
this.val = val == null ? 0 : val
this.left = left == null ? null : left
this.right = right == null ? null : right
}
}
有了这个节点类，我们就可以进行二叉树的构建了，定义一个类为BinaryTree，初始化根节点为null
class BinaryTree {
constructor() {
this.root = null
}
}
我们可以定义一个方法insert(val)来向数插入节点，首先需要判断是否根节点存在，如果不存在则插入节点为根节点，存在的话则通过和根节点比较，选择插入的位置。在比较时，执行下列步骤：
- 选定根节点
root，判断插入节点val和根节点值的大小 - 如果插入节点的值小于根节点，则往左查找根节点的左孩子。
- 如果左孩子不存在，则找到插入位置
- 如果左孩子存在，则将根节点设定为左孩子，回到1
- 如果插入节点的值大于根节点，则往右查找根节点的右孩子
- 如果右孩子不存在，则找到插入位置
- 如果右孩子存在，则将根节点设定为右孩子，回到1
function insert(val) {
if (!this.root) {
this.root = new TreeNode(val)
} else {
this.insertNode(this.root, val)
}
}
function insertNode(root, val) {
if (val < root.val) {
if (root.left == null) {
root.left = new TreeNode(val)
} else {
this.insertNode(root.left, val)
}
} else if (val > root.val) {
if (root.right == null) {
root.right = new TreeNode(val)
} else {
this.insertNode(root.right, val)
}
}
}
定义一个接收需要插入节点的值的数组，创建二叉树
function createBinaryTree(node_list) {
if (!node_list || !node_list.length) {
return null
}
for (let val of node_list) {
if (val) {
this.insert(val)
}
}
}
2. 递归方式遍历二叉树
二叉树的前中后序遍历是经典的三种遍历方式，我们可以用递归的方式，也可以用迭代的方式进行，下面先介绍递归的方式。
二叉树前序遍历是指我们对给定节点root，先获取该节点的值，再遍历其左子树，当完成左子树遍历后，遍历右子树，那么递归的方式可以理解为
print 根节点
遍历左子树
遍历右子树
具体代码如下
/**
* 递归前序遍历
* @param {TreeNode} root
*/
function preOrder(root) {
let res = []
const pre = (root) => {
if (!root) {
return
}
res.push(root.val)
pre(root.left) // 递归遍历左子树
pre(root.right) // 递归遍历右子树
}
pre(root)
return res
}
而中序遍历的顺序则是将print 根节点放在遍历完左子树后执行
遍历左子树
print 根节点
遍历右子树
后序遍历顺序则是将print 根节点放在遍历完右子树后执行
遍历左子树
遍历右子树
print 根节点
具体代码如下
/**
* 递归中序遍历
* @param {TreeNode} root
*/
function inOrder(root) {
let res = []
const midOrder = (root) => {
if (!root) {
return
}
midOrder(root.left)
res.push(root.val)
midOrder(root.right)
}
midOrder(root)
return res
}
/**
* 递归后续遍历
* @param {TreeNode} root
*/
function postOrder(root) {
let res = []
const posOrder = (root) => {
if (!root) {
return
}
posOrder(root.left)
posOrder(root.right)
res.push(root.val)
}
posOrder(root)
return res
}
3. 迭代方式遍历二叉树
递归方式代码比较简单，下面我们来看一下迭代方式遍历二叉树。由于递归的过程是一个入栈出栈的过程，那么我们可以知道迭代方式的话，需要显式维护一个栈，模拟递归的过程。
3.1 前序遍历
通过递归的过程我们可以知道，前序遍历是一种深度优先遍历，从根节点开始不断遍历左孩子，直到左孩子为空的时候停止，开始执行回归的过程，在回归的过程中，查找右孩子是否存在，存在的话又开始把右孩子作为根节点开始进行递归。
用栈来描述就是不断将左孩子入栈，如果左孩子为空则停止，此时开始出栈的过程，在出栈的时候判断是否右孩子存在，存在的话则将右孩子作为根节点入栈，又开始查找该右节点的左孩子。即回到了这段话的开头。
/**
* 用栈的方式进行前序遍历
* @param {TreeNode} root
*/
function preOrderByStack(root) {
if (!root) return []
let res = []
let stack = []
while (root || stack.length) {
// 根节点及左孩子入栈
while (root) {
res.push(root.val)
stack.push(root)
root = root.left
}
root = stack.pop()
// 查找右孩子是否存在，存在则遍历右孩子及右孩子的所有左孩子
root = root.right
}
return res
}
3.2 中序遍历
中序遍历的过程和前序遍历非常相似，从递归过程我们可以看出，中序遍历只是和前序遍历在输出根节点的时机上不同，此处不做赘述
/**
* 用栈的方式进行中序遍历
* @param {TreeNode} root
*/
function inOrderByStack(root) {
if (!root) return []
let res = []
let stack = []
while (root || stack.length) {
// 将根节点及其左孩子入栈
while (root) {
stack.push(root)
root = root.left
}
root = stack.pop()
res.push(root.val)
// 查找右孩子是否存在，存在则遍历右孩子及右孩子的所有左孩子
root = root.right
}
return res
}
3.3 后序遍历
后序遍历稍稍复杂，我们举一个例子来说明一下执行的过程
4
2 6
1 3 5 7
如上的一颗二叉树中，我们后续遍历的顺序是 1, 3, 2, 5, 7, 6, 4
即遍历是从下到上，从左到右的一个顺序
那么我们可以以根节点为分界线，把二叉树分为几个部分，即 中 - 左 - 右
为了保证输出顺序是 左 - 右 - 中，我们可以使得出栈顺序为 中 - 左 - 右
再将出栈的节点插入到数组的头部，则输出顺序就得到了保证
为了得到这个出栈的顺序，我们每当遇到中间节点入栈后，就可以将其出栈并插入到数组头部
然后按顺序入栈其左右节点，然后分别出栈添加到数组头部即可
代码如下
/**
* 使用单栈的方式进行后序遍历
* @param {TreeNOde} root
*/
function postOrderByOneStack(root) {
let res = [] // 保存结果。
let stack = [] // 使用栈进行遍历和输出结果。
root && stack.push(root) // 链表有值时才开始遍历。
// 不断遍历直到清空栈
while (stack.length) {
// 每次从栈中弹出一个节点，由于入栈顺序是从上到下，从左到右。
// 出栈顺序就会变成从上到下，从右到左。
const node = stack.pop()
// 由于最终输出的结果是从下到上，从左到右。
// 每次将弹出的节点插入到数组前端，即保证了最终输出的结果顺序。
res.unshift(node.val)
// 将子节点按照从左到右的顺序入栈，保证了输出顺序为从右到左。
node.left && stack.push(node.left)
node.right && stack.push(node.right)
}
return res
}
其实还有一种是采用双栈的方法，思路和单栈相同，也是为了保证输出顺序为左 - 右 - 中，需要第二个输出栈的出战顺序是中 - 右 - 左，而第一个栈则可以同单栈的思路一样，先出栈中到第二个栈，在分别入栈左接右并出栈到第二个栈，既可以保证第二个栈的输出顺序
/**
* 用栈的方式进行后序遍历
* @param {TreeNode} root
*/
postOrderByStack(root) {
if (!root) return []
let res = []
let stack1 = []
let stack2 = []
stack1.push(root)
while (stack1.length) {
root = stack1.pop()
stack2.push(root)
// 注意下面两个if的顺序不要反了
// 因为stack2中的入栈顺序是 中-右-左，所以stack1中关于左右的
// 入栈顺序应该是 左-右
if (root.left) {
stack1.push(root.left)
}
if (root.right) {
stack1.push(root.right)
}
}
while (stack2.length) {
res.push(stack2.pop().val)
}
return res
}
3.4 层序遍历
层序遍历实际上就是一层一层从上往下遍历，它的过程如下
4
2 6
1 3 5 7
加入4
退出4并进行遍历，加入2，6
退出2，6并进行遍历，加入1，3，5，7
退出1，3，5，7并进行遍历
我们注意到上述过程是一个先进先出的过程，所以这个地方可以采用队列来进行
/**
* 层序遍历，采用队列的方式进行广度优先搜索
* @param {TreeNode} root
*/
function levelSearch(root) {
if (!root) return []
let res = []
let queue = []
queue.push(root)
while (queue.length) {
let root = queue.shift()
res.push(root.val)
if (root.left) {
queue.push(root.left)
}
if (root.right) {
queue.push(root.right)
}
}
return res
}
顺便说个题外话，层序遍历我们可以用队列来做，能不能用双栈来做呢，即用双栈模拟队列的先进先出来实现？
最后贴一个完整代码
import { TreeNode } from './util.mjs'
class BinaryTree {
constructor() {
this.root = null
}
/**
* 构建二叉树
* @param {number[]} node_list
*/
createBinaryTree(node_list) {
if (!node_list || !node_list.length) {
return null
}
for (let val of node_list) {
if (val) {
this.insert(val)
}
}
}
/**
*
* @param {number} val
*/
insert(val) {
if (!this.root) {
this.root = new TreeNode(val)
} else {
this.insertNode(this.root, val)
}
}
/**
*
* @param {TreeNode} root
* @param {number} val
*/
insertNode(root, val) {
if (val < root.val) {
if (root.left == null) {
root.left = new TreeNode(val)
} else {
this.insertNode(root.left, val)
}
} else if (val > root.val) {
if (root.right == null) {
root.right = new TreeNode(val)
} else {
this.insertNode(root.right, val)
}
}
}
/**
* 递归前序遍历
* @param {TreeNode} root
*/
preOrder(root) {
let res = []
const pre = (root) => {
if (!root) {
return
}
res.push(root.val)
pre(root.left)
pre(root.right)
}
pre(root)
return res
}
/**
* 递归中序遍历
* @param {TreeNode} root
*/
inOrder(root) {
let res = []
const midOrder = (root) => {
if (!root) {
return
}
midOrder(root.left)
res.push(root.val)
midOrder(root.right)
}
midOrder(root)
return res
}
/**
* 递归后续遍历
* @param {TreeNode} root
*/
postOrder(root) {
let res = []
const posOrder = (root) => {
if (!root) {
return
}
posOrder(root.left)
posOrder(root.right)
res.push(root.val)
}
posOrder(root)
return res
}
/**
* 用栈的方式进行前序遍历
* @param {TreeNode} root
*/
preOrderByStack(root) {
if (!root) return []
let res = []
let stack = []
while (root || stack.length) {
// 根节点及左孩子入栈
while (root) {
res.push(root.val)
stack.push(root)
root = root.left
}
root = stack.pop()
// 查找右孩子是否存在，存在则遍历右孩子
root = root.right
}
return res
}
/**
* 用栈的方式进行中序遍历
* @param {TreeNode} root
*/
inOrderByStack(root) {
if (!root) return []
let res = []
let stack = []
while (root || stack.length) {
// 将根节点及其左孩子入栈
while (root) {
stack.push(root)
root = root.left
}
root = stack.pop()
res.push(root.val)
// 此时需要遍历右孩子
root = root.right
}
return res
}
/**
* 用栈的方式进行后序遍历
* @param {TreeNode} root
*/
postOrderByStack(root) {
if (!root) return []
let res = []
let stack1 = []
let stack2 = []
stack1.push(root)
while (stack1.length) {
root = stack1.pop()
stack2.push(root)
// 注意下面两个if的顺序不要反了
// 因为stack2中的入栈顺序是 中-右-左，所以stack1中关于左右的
// 入栈顺序应该是 左-右
if (root.left) {
stack1.push(root.left)
}
if (root.right) {
stack1.push(root.right)
}
}
while (stack2.length) {
res.push(stack2.pop().val)
}
return res
}
/**
* 使用单栈的方式进行后序遍历
* @param {TreeNOde} root
*/
postOrderByOneStack(root) {
let res = [] // 保存结果。
let stack = [] // 使用栈进行遍历和输出结果。
root && stack.push(root) // 链表有值时才开始遍历。
// 不断遍历直到清空栈
while (stack.length) {
// 每次从栈中弹出一个节点，由于入栈顺序是从上到下，从左到右。
// 出栈顺序就会变成从上到下，从右到左。
const node = stack.pop()
// 由于最终输出的结果是从下到上，从左到右。
// 每次将弹出的节点插入到数组前端，即保证了最终输出的结果顺序。
res.unshift(node.val)
// 将子节点按照从左到右的顺序入栈，保证了输出顺序为从右到左。
node.left && stack.push(node.left)
node.right && stack.push(node.right)
}
return res
}
/**
* 层序遍历，采用队列的方式进行广度优先搜索
* @param {TreeNode} root
*/
levelSearch(root) {
if (!root) return []
let res = []
let queue = []
queue.push(root)
while (queue.length) {
let root = queue.shift()
res.push(root.val)
if (root.left) {
queue.push(root.left)
}
if (root.right) {
queue.push(root.right)
}
}
return res
}
}
// test
const tree = new BinaryTree()
tree.createBinaryTree([4, 2, 6, 1, 3, 5, 7])
/**
* 4
* 2 6
* 1 3 5 7
*/
// console.log(tree.preOrder(tree.root)) // 4, 2, 1, 3, 6, 5, 7
// console.log(tree.inOrder(tree.root)) // 1, 2, 3, 4, 5, 6, 7
// console.log(tree.postOrder(tree.root)) // 1, 3, 2, 5, 7, 6, 4
console.log(tree.preOrderByStack(tree.root)) // 4, 2, 1, 3, 6, 5, 7
console.log(tree.inOrderByStack(tree.root)) // 1, 2, 3, 4, 5, 6, 7
console.log(tree.postOrderByStack(tree.root)) // 1, 3, 2, 5, 7, 6, 4
console.log(tree.postOrderByOneStack(tree.root)) // 1, 3, 2, 5, 7, 6, 4
console.log(tree.levelSearch(tree.root)) // 4, 2, 6, 1, 3, 5, 7
