1.是什么
- 一种分层数据的抽象模型。
- 前端工作中常见的树包括：DOM
2. 常用操作
深度/广度优先遍历、先中后序遍历。
2.1. 树的深度与广度优先遍历
- 深度优先遍历：尽可能深的搜索树的分支。
如下图：
- 广度优先遍历：先访问离根节点最近的节点
如下图：
深度优先遍历算法口诀（递归）
- 访问根节点。
- 对根节点的 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.forEach((child) => dfs(child))
}
dfs(tree) // a b d e c f g
广度优先遍历算法口诀
- 新建一个队列，把根节点入队。
- 把队头出队并访问。
- 把队头的 children 挨个入队。
- 重复第二、三步，直到队列为空
const bfs = (root) => {
let queue = [];
queue.push(root);
while(queue.length > 0) {
let n = queue.shift()
console.log(n.val)
n.children.forEach(child => queue.push(child))
}
}
bfs(tree) // a b c d e f g
2.2. 二叉树的先中后序遍历（递归版）
2.2.1. 是什么？
- 树中每个节点最多只能有两个子节点。
- 在 js 中通常用 Object 来模拟二叉树
const binaryTree = {
val: 1,
left: {
val: 1,
left: null,
right: null
},
right: {
val: 3,
left: null,
right: null
}
}
2.2.2 先序遍历算法口诀
- 访问根节点
- 对根节点的左子树进行先序遍历。
- 对根节点的右子树进行先序遍历。
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
}
}
}
module.exports = bt
- preorder.js
const bt = require('./bt');
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
2.2.3 中序遍历算法口诀
- 对根节点的左子树进行中序遍历。
- 访问根节点。
- 对根节点的右子树进行中序遍历。
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
上面代码执行顺序如下，每次调用 inorder 就会在栈里添加一个内存
1). 第一次调用 inorder 传入 bt 的时候
栈里加入一个 inorder ，root 为 bt
2). 因为root有值所以继续调用 inorder(root.left) 此时又向栈里添加了一个 inorder 内存，root 为 {val: 2}，如下图
3). root有值继续调用 inorder(root.left)，再次栈里添加一个 inorder，新的 root 为 {val: 4}
4). root 有值，继续执行 inorder(root.left)，添加一个 inorder，新的 root 为 null
5). root没值，当前 inorder 执行完成从栈里移出，当前 root 就变成了上一个的也就是 {val: 4}
6). 打印出出root.val 也就是4，然后继续调用 inorder(root.right) 在栈里添加一个 inorder 内存, root.right 的值是null
7). root 没值当前栈直接return 从栈里移出，然后它的上一个也跟着执行完成从栈里移出，此时栈顶元素变成了 {val: 2}
8). root.right 的值为 {val: 5}，栈里新加一个 inorder(root.right)
9). 执行到 inorder.left 再次向栈里添加一个内存 值为 null 然后从内存里移出，上一个也跟着结束移出，此时顶层就变成了 {val: 2}
....
2.2.4. 后序遍历算法口诀
- 对根节点的左子树进行后序遍历。
- 对根节点的右子树进行后序遍历。
- 访问根节点。
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
2.3. 二叉树的先中后序遍历（非递归版）
因为递归的本质就是栈的调用，每次往栈里添加一个函数，函数执行完紧接着从这个栈里移出，所以我们可以用栈模拟递归
- 先序遍历
const preorder = (root) => {
if (!root) return;
const stack = [];
stack.push(root);
while(stack.length > 0) {
const n = stack.pop();
console.log(n.val);
// 之所以先push right 是因为 栈后进先出，left 后进的可以先出来
n.right && stack.push(n.right);
n.left && stack.push(n.left)
}
}
- 中序遍历
左根右的顺序
const inorder = (root) => {
// 1.一进来先把所有当前节点的左节点递归遍历完
inorder(root.left);
// 2. 然后获取到当前节点的最底层左节点
console.log(root.val);
// 3. 拿到当前最底层左节点的右节点，然后重复1、2步（把当前右节点作为根节点获取所有的左节点，获取当前节点），
inorder(root.right);
}
const inorder = (root) => {
if (!root) return;
const stack = [];
let p = root;
while(stack.length || p) {
// 1. 获取根节点的所有左节点
while(p) {
stack.push(p);
p = p.left;
}
// 2. 获取最底层的左节点
const n = stack.pop();
console.log(n.val);
// 获取最底层左节点的右节点，重复1、2步
p = n.right
}
}
以上面的二叉树为例分析代码执行顺序
root 是最外层也就是 {val: 1}，当前 p 为 {val: 1} 进入循环，stack 里 push 后为 [{val: 1}], p.left 为 {val: 2} 继续循环 stack 里 push 后为 [{val: 1}, {val: 2}], p.left 为 {val: 4}， 继续循环 stack push 后为 [{val: 1}, {val: 2}, {val: 4}]，p.left 为 null 退出循环，stack.pop 为 {val: 4}，它的right为null，p 为 null，回到最外层的循环，内层 p 为 null 不进入，直接 获取 stack.pop 为{val: 2}，它的right 也就是p是 {val: 5}，进入内层循环， stack push 后为[{val: 1}, {val: 5}], {val: 5} 的left 是 null，退出内层循环，stack.pop 获取到{val: 5}，它的right也是 null，p 为 null 不进入内层循环，stack.pop 为 {val: 1}
- 后序遍历
把后序遍历的顺序倒置一下，按照先序遍历的逻辑，实现逆序的访问，再利用栈的后进先出特性，把先序的顺序倒置过来，重新访问就可以
const postorder = (root) => {
if (!root) return
const stack = [];
const outputStack = [];
stack.push(root);
while(stack.length > 0) {
const n = stack.pop();
outputStack.push(n)
n.left && stack.push(n.left);
n.right && stack.push(n.right);
}
while(outputStack.length) {
const n = outputStack.pop();
console.log(n.val)
}
}
2.4. 二叉树的最大深度 leetCode 104
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路
解题步骤
var maxDepth = function(root) {
let res = 0;
let dfs = (node, level) => {
if (!node) return;
if (!node.left && !node.right) {
res = Math.max(res, level)
}
dfs(node.left, level + 1);
dfs(node.right, level + 1)
}
dfs(root, 1)
return res
};
时间复杂度就是 O(n)，空间复杂度因为我们里面用到了递归，每次调用函数都会被放到栈里，函数没有执行完都会存在内存里，所以我们只需要知道这个递归的树节点一共嵌套了多少层就可以，也就是二叉树的最大深度，最坏的情况的节点数就等于最大深度也就是O(n)，最好的情况下Ologn
2.5. 二叉树的最小深度 leetCode 111
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
解题思路
解题步骤
var minDepth = function(root) {
if (!root) return 0;
const queue = [];
// 每次push的时候顺便把当前的层级带上
queue.push([root, 1]);
while(queue.length) {
const [n, level] = queue.shift();
if (!n.left && !n.right) {
return level
}
n.left && queue.push([n.left, level + 1])
n.right && queue.push([n.right, level + 1]);
}
};
时间复杂度O(n) 空间复杂度O(n)
2.6. 二叉树的层序遍历 leetCode 102
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
解题思路
解题步骤
var levelOrder = function(root) {
if (!root) return [];
const queue = [[root, 0]]
const res = [];
while(queue.length) {
const [n, level] = queue.shift();
if (!res[level]) {
res[level] = []
}
res[level].push(n.val)
n.left && queue.push([n.left, level + 1]);
n.right && queue.push([n.right, level + 1]);
}
return res;
};
时间复杂度和空间复杂度都是O(n)
2.7. 二叉树的中序遍历 leetCode 94
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
递归版
var inorderTraversal = function(root) {
const res = [];
const rec = (node) => {
if (!node) return;
rec(node.left);
res.push(node.val);
rec(node.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 node = stack.pop();
res.push(node.val);
p = node.right
}
return res;
};
2.8. 路径和总和 leetCode 112
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解题思路：
解题步骤：
var hasPathSum = function(root, targetSum) {
if (!root) return false;
let res = false;
const dfs = (node, sum) => {
if (!node.left && !node.right && sum === targetSum) {
res = true;
}
console.log(node.val)
if (node.left) dfs(node.left, sum + node.left.val);
if (node.right) dfs(node.right, sum + node.right.val);
};
dfs(root, root.val);
return res;
};
时间复杂度 O(n) 空间复杂度最差 O(n) 最好 O(logn)
2.9 遍历 JSON 的所有节点值
const json = {
a: { b: { c: 1 } },
d: [1, 2]
};
const dfs = (n, path) => {
Object.keys(n).forEach(k => {
dfs(n[k], path.concat(k))
});
}
dfs(json, []);
