树
- 一种分层数据的抽象模型
- 前端工作中常见的树包括：DOM树、级联选择器、树形控件
- JS中没有树，但是可以用Object和Array构建树
- 树的常用操作：深度/广度优先遍历、先中后序遍历
树的深度与广度优先遍历
-
深度优先遍历：尽可能深的搜索树的分支
image.png -
广度优先遍历：先访问离根节点最近的节点
image.png
深度优先遍历
- 访问根节点
- 对根节点的children挨个进行深度优先遍历
- 递归
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'f',
children: []
}
]
}
]
}
const dfs = (root) => {
console.log(root)
root.children.forEach(dfs)
}
dfs(tree)
广度优先遍历
- 新建一个队列，把根节点入队
- 把队头出队并访问
- 把队头的children挨个入队
- 重复第二步、第三步直到队列为空
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'f',
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)
二叉树
- 树中每个节点最多只能有两个子节点
- 在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
}
}
}
先序遍历
- 访问根节点
- 对根节点的左子树进行先序遍历
- 对根节点的右子树进行先序遍历
image.png
const preorder = (root) => {
if (!root) return
console.log(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(bt)
中序遍历
- 对根节点的左子树进行中序遍历
- 访问根节点
- 对根节点的右子树进行中序遍历
image.png
const inorder = (root) => {
if (!root) return
inorder(root.left)
console.log(root.val)
inorder(root.right)
}
inorder(bt)
后序遍历
- 对根节点的左子树进行后序遍历
- 对根节点的右子树进行后序遍历
- 访问根节点
image.png
const postorder = (root) => {
if (!root) return
postorder(root.left)
postorder(root.right)
console.log(root.val)
}
postorder(bt)
二叉树的先中后序遍历（非递归）
二叉树先序遍历
// 递归版
const preorder = root => {
...
preorder(...)
...
}
如果在函数里面，调用另外一个函数，就会形成一个函数调用堆栈，调用完毕后又被释放
所以说，堆栈就是我们实现非递归版先中后序遍历的关键，我们可以用堆栈来模拟递归操作
const preorder = root => {
if (!root) return
const stack = [root]
while (stack.length) {
const n = stack.pop()
console.log(n)
if (n.right) stack.push(n.right)
if (n.left) stack.push(n.left)
}
}
二叉树中序遍历
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
}
}
二叉树后序遍历
const postorder = root => {
if (!root) return
const stack = [root]
const outputStack = []
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)
}
}
二叉树的最大深度
- 求最大深度，考虑使用深度优先遍历
- 在深度优先遍历过程中，记录每个节点所在层级，找出最大层级
// 104.二叉树的最大深度
var 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
};
二叉树的最小深度
思路：
- 求最小深度，考虑使用广度优先遍历
- 在广度优先遍历过程中，遇到叶子节点停止遍历，返回节点层级
解题步骤：
- 广度优先遍历整棵树，并记录每个节点的层级
- 遇到叶子节点，返回节点层级，停止遍历
// 111.二叉树的最小深度
var minDepth = function(root) {
if (!root) {return 0}
const q = [[root, 1]]
while (q.length > 0) {
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])
}
};
二叉树的层序遍历
- 层序遍历顺序就是广度优先遍历
- 不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中
// 102.二叉树的层序遍历
var levelOrder = function(root) {
if (!root) return []
const q = [root]
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
};
二叉树的中序遍历
// 94.二叉树的中序遍历
// 递归
var 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
};
// 非递归
var 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
};
路径总和
- 在深度优先遍历的过程中，记录当前路径的节点值的和
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值
// 112.路径总和
var hasPathSum = function(root, targetSum) {
if (!root) return false
let result = false
const dfs = (n, val) => {
if (!n.left && !n.right && val === targetSum) result = true
if (n.left) dfs(n.left, n.left.val + val)
if (n.right) dfs(n.right, n.right.val + val)
}
dfs(root, root.val)
return result
};
遍历JSON的所有节点值
const json = {
a: {
b: {
c: 1
}
},
d: [1, 2]
}
dfs = (n, path) => {
console.log(n)
Object.keys(n).forEach(k => {
dfs(n[k], path.concat(k))
})
}
dfs(json, [])
总结
- 树是一种分层数据的抽象模型，在前端广泛应用
- 树的常用操作：深度/广度优先遍历、先中后序遍历...
