# 介绍
- 掌握
- 遍历方法：前序、中序、后序、深度优先、广度优先
- 递归求解
# 前中后序遍历
- 前：根 -> 左 -> 右
- 中：左 -> 根 -> 右
- 后：左 -> 右 -> 根
// 前序
const root = [1,null,2]; // 注：不是数组，是treeNode节点
console.log(preorderTraversal(root)); // [1,2]
1
2
3
2
3
时间：91.23%
空间：51.89%
function preorderTraversal(root, ans = []) {
if (!root) {
return [];
}
ans.push(root.val);
preorderTraversal(root.left, ans);
preorderTraversal(root.right, ans);
return ans;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
时间：99.53%
空间：41.18%
function inorderTraversal(root, ans = []) {
if (!root) {
return [];
}
inorderTraversal(root.left, ans);
ans.push(root.val);
inorderTraversal(root.right, ans);
return ans;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
时间：99.51%
空间：57.67%
function postorderTraversal(root, ans = []) {
if (!root) {
return [];
}
postorderTraversal(root.left, ans);
postorderTraversal(root.right, ans);
ans.push(root.val);
return ans;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 广度优先
- 广度优先：利用队列，又叫做层序遍历
- 深度优先：利用递归
- 广度优先：力扣102 (opens new window)
- 深度优先：
时间：92.31%
空间：34.92%
function levelOrder(root) {
if (!root) {
return [];
}
const ans = [];
const queue = [];
queue.push(root);
let len = queue.length;
while (len) {
let cLevel = [];
for (let i = 0; i < len; i++) {
const cNode = queue.shift();
cLevel.push(cNode.val);
if (cNode.left) {
queue.push(cNode.left);
}
if (cNode.right) {
queue.push(cNode.right);
}
}
ans.push(cLevel);
len = queue.length;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 最大深度
- 给定二叉树求最大深度
- 力扣104 (opens new window)
时间：88.43%
空间：98.00%
function maxDepth(root, max = 0) {
if (!root) {
return max;
}
return Math.max(maxDepth(root.left, max + 1), maxDepth(root.right, max + 1));
}
1
2
3
4
5
6
2
3
4
5
6
# 路径总和
- 求路径总和是否等于target值
const root = [5,4,8,11,null,13,4,7,2,null,null,null,1];
const targetSum = 22;
console.log(hasPathSum(root, targetSum)); // true
1
2
3
2
3
- 深度优先遍历
时间：98.10%
空间：45.77%
function hasPathSum(root, targetSum) {
if (!root) {
return false;
}
// 叶子节点，递归终点判断
if (!root.left && !root.right) {
return targetSum === root.val;
}
return !!(hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val));
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 根据中序后序构造二叉树
- 给定中序、后序遍历
- 假定没有重复元素
- 构造二叉树
- 力扣106 (opens new window)
- 后序遍历最后一个是根
- 中序遍历中根为中线，左右叉树可以划分
- 右叉树不为0，拿再拿后序遍历的倒数第二个就是右叉树的根
- 以此类推
时间：40.65%
空间：15.11%
function buildTree(inorder, postorder) {
if (inorder.length === 1) {
return new TreeNode(inorder[0], null, null);
}
const rootVal = postorder[postorder.length - 1];
const rootNode = new TreeNode(rootVal, null, null);
const rootIndex = inorder.indexOf(rootVal);
let inorderLeft = inorder.slice(0, rootIndex);
let inorderRight = inorder.slice(rootIndex + 1, postorder.length);
if (inorderRight.length) {
rootNode.right = buildTree(inorderRight, postorder.slice(postorder.length - inorderRight.length - 1, postorder.length - 1));
}
if (inorderLeft.length) {
rootNode.left = buildTree(inorderLeft, postorder.slice(0, inorderLeft.length));
}
return rootNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- 利用哈希表存储中序遍历，然后用下标记录本树的边界，进行递归
时间：97.03%
空间：63.49%
function buildTree(inorder, postorder) {
// 用来取中点，提高效率
const inorderMap = new Map(inorder.map((item, index) => [item, index]));
const handler = (left, right) => {
if (left > right) {
return null;
}
const nodeVal = postorder[rootIndex--];
const index = inorderMap.get(nodeVal);
const node = new TreeNode(nodeVal);
// 左右边界去掉当前节点
node.right = handler(index + 1, right);
node.left = handler(left, index - 1);
return node;
}
let rootIndex = postorder.length - 1;
return handler(0, inorder.length - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 前序中序构造二叉树
- 给前序中序遍历
- 返回二叉树
- 力扣105 (opens new window)
- 同前面的优化思路，拿一个map存储中序键值对，查下标时间变成O(1)。再用前序找根，中序分左右子树的方法做出二叉树
- 注：后序应该先把右子树做完，前序应该先把左子树做完。
时间：97.06%
空间：63.13%
function buildTree(preorder, inorder) {
const inorderMap = new Map(inorder.map((item, index) => [item, index]));
const handler = (left, right) => {
if (left > right) {
return null;
}
const nodeVal = preorder[rootIndex++];
const node = new TreeNode(nodeVal);
const index = inorderMap.get(nodeVal);
node.left = handler(left, index - 1);
node.right = handler(index + 1, right);
return node;
}
let rootIndex = 0;
return handler(rootIndex, preorder.length - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 填充所有节点的右侧指针
- 给完美二叉树
- 同级的节点左边指右边，最右边指null
- 力扣116 (opens new window)
时间：99.30%
空间：35.50%
function connect(root) {
if (!root) {
return null;
}
const queue = [];
queue.push(root);
let len = queue.length;
while (len) {
for (let i = 0; i < len; i++) {
const cNode = queue.shift();
cNode.next = i !== len - 1 ? queue[0] : null;
if (cNode.left) {
queue.push(cNode.left);
}
if (cNode.right) {
queue.push(cNode.right);
}
}
len = queue.length;
}
return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- 做一个左右节点指针器
时间：97.15%
空间：91.19%
function connect(root) {
if (!root) {
return null;
}
const handler = (left, right) => {
if (!left || left.next === right) {
return;
}
left.next = right;
handler(left.left, left.right);
handler(left.right, right.left);
handler(right.left, right.right);
}
handler(root.left, root.right);
return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17