树
- 一种分层数据的抽象模型
- 前端工作中常见的数包括：DOM树、级联选择、树形控件…
- javascript中没有树，但是可以用Object和Array构建树
- 树的常用操作：深度/广度优先遍历、先中后序遍历
树的深度与广度优先遍历
深度优先遍历：尽可能深的搜索树的分支
深度优先遍历
广度优先遍历：先访问离根节点最近的节点
广度优先遍历
深度优先遍历(dfs)算法口诀
- 访问根节点
- 对根节点的children挨个进行深度优先遍历
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{ val: 'd', children: [] },
{ val: 'e', children: [] }
]
}, {
val: 'c',
children: [
{ val: 'f', children: [] },
{ val: 'g', children: [] }
]
}
]
}
const dfs = (root) => {
console.log(root.val)
root.children && root.children.forEach(dfs) // 防止初学者懵逼，相当于 root.children.forEach(child => dfs(child))
}
dfs(tree) // a b d e c f g
广度优先遍历(bfs)算法口诀
- 新建一个队列，把根节点入队
- 把队头出队并访问
- 把对头的children挨个入队
- 重复第二、三步，直到队列为空
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{ val: 'd', children: [] },
{ val: 'e', children: [] }
]
}, {
val: 'c',
children: [
{ val: 'f', children: [] },
{ val: 'g', children: [] }
]
}
]
}
const bfs = (root) => {
const q = [root]
while (q.length > 0) {
const n = q.shift()
console.log(n.val)
n.children.forEach(child => q.push(child))
}
}
bfs(tree) // a b c d e f g
二叉树的先中后序遍历（递归实现）
二叉树
- 树中每个节点最多只能有两个子节点
- 在JS中通常使用Object来模拟二叉树
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null
},
right: {
val: 5,
left: null,
right: null
}
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null
},
right: {
val: 7,
left: null,
right: null
}
}
}
先序遍历(preorder)算法口诀
- 访问根节点
- 对根节点的左子树进行先序遍历
- 对根节点的右子树进行先序遍历
先序遍历
const preorder = root => {
if (!root) return
console.log(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(bt) // 1 2 4 5 3 6 7
中序遍历(inorder)算法口诀
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
中序遍历
// bt同上，省略不写
const inorder = root => {
if (!root) return
inorder(root.left)
console.log(root.val)
inorder(root.right)
}
inorder(bt) // 4 2 5 1 6 3 7
后续遍历算法口诀
- 对根节点的左子树进行后续遍历
- 对根节点的右子树进行后续遍历
- 访问根节点
后续遍历
// bt同上，省略不写
const postorder = root => {
if (!root) return
postorder(root.left)
postorder(root.right)
console.log(root.val)
}
postorder(bt) // 4 5 2 6 7 3 1
二叉树的先中后序遍历（非递归实现）
先序遍历
const preorder = root => {
if (!root) return
const stack = [root]
while (stack.length) {
const n = stack.pop()
console.log(n.val)
if (n.right) stack.push(n.right)
if (n.left) stack.push(n.left)
}
}
preorder(bt) // 1 2 4 5 3 6 7
中序遍历
const inorder = root => {
if (!root) return
const stack = []
let p = root
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
console.log(n.val)
p = n.right
}
}
inorder(bt) // 4 2 5 1 6 3 7
后序遍历
- 复用先序遍历
- 访问操作改成入栈操作
- 通过栈的特点输出实现逆序
const postorder = root => {
if (!root) return
const outputStack = []
const stack = [root]
while (stack.length) {
const n = stack.pop()
outputStack.push(n)
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
while(outputStack.length) {
const n = outputStack.pop()
console.log(n.val)
}
}
postorder(bt) // 4 5 2 6 7 3 1
二叉树的最大深度
- 求最大深度，考虑使用深度优先遍历
- 在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
/**
* 通过一个层次遍历的数组生成一棵二叉树
* @param {any[]} array
* @return {TreeNode}
*/
function getTreeFromLayerOrderArray(array) {
let n = array.length;
if (!n) return null;
let index = 0;
let root = new TreeNode(array[index++]);
let queue = [root];
while(index < n) {
let top = queue.shift();
let v = array[index++];
top.left = v == null ? null : new TreeNode(v);
if (index < n) {
let v = array[index++];
top.right = v == null ? null : new TreeNode(v);
}
if (top.left) queue.push(top.left);
if (top.right) queue.push(top.right);
}
return root;
}
/**
* 访问根节点
* 对根节点的children挨个进行深度优先遍历
*
* @param {TreeNode} root
* @return {number}
*/
const maxDepth = function(root) {
let res = 0
const dfs = (n, l) => {
if (!n) return
if (!n.left && !n.right) { // 叶子节点，证明到达最大深度
res = Math.max(res, l)
}
dfs(n.left, l + 1)
dfs(n.right, l+ 1)
}
dfs(root, 1)
return res
}
const btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(maxDepth(btTree))
二叉树的最小深度
- 求最小深度，考虑使用广度优先遍历
- 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级
/**
* 新建一个队列，把根节点入队
* 把队头出队并访问
* 把对头的children挨个入队
* 重复第二、三步，直到队列为空
*
* @param {TreeNode} root
* @return {number}
*/
const minDepth = function(root) {
if (!root) return 0
const q = [[root, 1]]
while (q.length) {
const [n, l] = q.shift()
if (!n.left && !n.right) { // 到达叶子节点
return l
}
if (n.left) q.push([n.left, l + 1])
if (n.right) q.push([n.right, l + 1])
}
}
const btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(minDepth(btTree))
二叉树的层序遍历
- 层次遍历顺序就是广度优先遍历
- 在遍历时需要记录当前节点所处的层级，方便将其添加到不同的数组中
/**
* @param {TreeNode} root
* @return {number[][]}
*/
// 方法一
const levelOrder = function(root) {
if (!root) return []
const q = [[root, 0]]
const res = []
while (q.length) {
const [n, level] = q.shift()
if (!res[level]) {
res.push([n.val])
} else {
res[level].push(n.val)
}
if (n.left) q.push([n.left, level + 1])
if (n.right) q.push([n.right, level + 1])
}
return res
}
// 方法二
const levelOrder = function(root) {
if (!root) return []
const q = [root, 0]
const res = []
while (q.length) {
let len = q.length
res.push([])
while (len--) {
const n = q.shift()
res[res.length - 1].push(n.val)
if (n.left) q.push(n.left)
if (n.right) q.push(n.right)
}
}
return res
}
const btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(levelOrder(btTree))
二叉树的中序遍历
- 完全就是上面的中序遍历解法
/**
* @param {TreeNode} root
* @return {number[]}
* @descript 递归版
*/
const inorderTraversal = function(root) {
const res = []
const rec = n => {
if (!n) return
rec(n.left)
res.push(n.val)
rec(n.right)
}
rec(root)
return res
}
/**
* @param {TreeNode} root
* @return {number[]}
* @descript 迭代版
*/
const inorderTraversal = function(root) {
const res = []
const stack = []
let p = root
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
res.push(n.val)
p = n.right
}
return res
}
const btTree = getTreeFromLayerOrderArray([1, null, 2, 3])
console.log(inorderTraversal(btTree))
路径总和
- 在深度优先遍历的过程中，记录当前路径的节点值的和
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
const hasPathSum = function(root, targetSum) {
if (!root) return false
let res = false
const dfs = (n, s) => {
if (!n.left && !n.right && s === targetSum) { // 叶子节点并且值等于目标值
res = true
}
if (n.left) dfs(n.left, s + n.left.val)
if (n.right) dfs(n.right, s + n.right.val)
}
dfs(root, root.val)
return res
}
const btTree = getTreeFromLayerOrderArray([5,4,8,11,null,13,4,7,2,null,null,null,1])
console.log(hasPathSum(btTree, 22))
遍历json的所有节点值
- 深度优先遍历
const json = {
a: { b: { c: 1 } },
d: [1, 2]
}
const dfs = (n, path) => {
console.log((!path.length ? 'root' : path.join('.')) + '的值是：' + JSON.stringify(n))
Object.keys(n).forEach(k => {
dfs(n[k], path.concat(k))
})
}
dfs(json, [])
// root的值是：{"a":{"b":{"c":1}},"d":[1,2]}
// a的值是：{"b":{"c":1}}
// a.b的值是：{"c":1}
// a.b.c的值是：1
// d的值是：[1,2]
// d.0的值是：1
// d.1的值是：2
