先序遍历
先序遍历算法口诀
- 访问 根 节点
- 对根节点的 左 子树进行先序遍历
- 对根节点的 右 子树进行先序遍历
图示：
1
/ \
2 3
/ \ / \
4 5 6 7
const bt = require('./bt')
preorder(bt) // 1,2,4,5,3,6,7
迭代版本
/**
* 先序遍历
* 核心就是：根 - 左 - 右
* @param {*} root
* @returns
*/
function preorder(root) {
if (!root) return
// 1.访问 根 节点
console.log(root.val)
// 2.对根节点的 左 子树进行先序遍历
preorder(root.left)
// 3.对根节点的 右 子树进行先序遍历
preorder(root.right)
}
非递归实现，迭代实现
/**
* 先序遍历
* 核心就是：根 - 左 - 右
* @param {*} root
* @returns
*/
function preorder(root) {
// 用来暂存节点的栈
const stack = []
// 新建一个游标节点为根节点
let node = root
// 当遍历到最后一个几点时，若它的左、右子树都为空，并且栈也为空
// 则只需要不同时满足这两点，都需要进入循环
while (node != null || stack.length > 0) {
// 若当前考查节点非空，则输出该节点的值
// 由考查顺序可知，需要一直往左走
while (node != null) {
console.log(node.val)
// 为了之后能找到该节点的右子树，暂存该节点
stack.push(node)
node = node.left
}
// 一直到左子树为空，则开始考虑右子树
// 弹出栈顶元素，将游标等于该节点的右子树
if (stack.length > 0) {
node = stack.pop()
node = node.right
}
}
}
中序遍历
中序遍历算法口诀
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
图示
1
/ \
2 3
/ \ / \
4 5 6 7
const bt = require('./bt')
inorder(bt) // 4,2,5,1,6,3,7
迭代方案
/**
* 中序遍历
* 左-根-右
*
* @param {*} root
* @returns
*/
function inorder(root) {
if (!root) return
// 1.对根节点的左子树进行中序遍历
inorder(root.left)
// 2.访问根节点
console.log(root.val)
// 3.对根节点的右子树进行中序遍历
inorder(root.right)
}
非递归实现，迭代实现
/**
* 中序遍历
* 左-根-右
*
* @param {*} root
* @returns
*/
function inorder(root) {
if (!root) return
const stack = []
let node = root;
while (node != null || stack.length > 0) {
// 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
while (node != null) {
stack.push(node)
// 1.对根节点的左子树进行中序遍历
node = node.left
}
if (stack.length > 0) {
node = stack.pop()
// 2.访问节点
console.log(node.val)
// 3.对根节点的右子树进行中序遍历
node = node.right
}
}
}
后序遍历
后序遍历算法口诀
- 对根节点的左子树进行后序遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
图示
1
/ \
2 3
/ \ / \
4 5 6 7
const bt = require('./bt')
postorder(bt) // 4,5,2,6,7,3,1
迭代版本
/**
* 后序遍历
* 左-右-根
*
* @param {*} root
* @returns
*/
function postorder(root) {
if (!root) return
// 1.对根节点的左子树进行后序遍历
postorder(root.left)
// 2.对根节点的右子树进行后序遍历
postorder(root.right)
// 3.访问根节点
console.log(root.val)
}
非递归实现，迭代实现
/**
* 后序遍历
* 左-右-根
*
* @param {*} root
* @returns
*/
function postorder(root) {
const stack = []
let node = root
let visit = root
while (node != null || stack.length > 0) {
while (node != null) {
stack.push(node)
node = node.left
}
// 查看当前栈顶元素
node = stack[stack.length - 1]
// 如果其右子树也为空，或者右子树已经访问
// 则可以直接输出当前节点的值
if (node.right == null || node.right === visit) {
console.log(node.val)
stack.pop()
visit = node
node = null
} else {
// 否则继续遍历右子树
node = node.right
}
}
}