# 第3章非线性结构算法题

3-1 二叉树层序遍历-读题
3-2 二叉树层序遍历-通过数组构建二叉树-思路
3-3 二叉树层序遍历-通过数组构建二叉树-实现
3-4 二叉树层序遍历-二叉树遍历
3-5 二叉树层序遍历-解题
3-6 N叉树的层序遍历-读题
3-7 N叉树的层序遍历-递归解
3-8 N叉树的层序遍历-bfs解
3-9 N叉树的层序遍历-dfs解

# 3-1 二叉树层序遍历-读题

问题：

来源：LeetCode (opens new window)

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

示例: 给定二叉树: [3,9,20,null,null,15,7],

/
9 20 /
15 7 返回其层次遍历结果：

[ [3], [9,20], [15,7] ]

分析：

理解二叉树的数组表示法。

构建二叉树
先通过数组构建一棵二叉树，参考 (opens new window)
树的中序遍历
遍历树并记录层级

回顾：

构建二叉树

//TreeNode.ts
export default class TreeNode<T> {
  val: T;
  left: TreeNode<T>;
  right: TreeNode<T>;
  constructor(item: T) {
    this.val = item;
    this.left = null;
    this.right = null;
  }
}

//构建二叉树 
//     1
//    / \
//   2   3
const tree = new TreeNode(1);
const left = new TreeNode(2);
const right = new TreeNode(3);
tree.left = left;
tree.right = right;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 3-2 二叉树层序遍历-通过数组构建二叉树-思路

问题：

如何通过数组构建二叉树

参考 leetcode 说明 (opens new window)

分析：

找规律：

规律1:index 为奇数的为左子树，index 非0的偶数节点为右子树
规律2:节点按照创建的顺序做为父节点挂载子节点，
规律3:每个节点都是 2 次作为父节点（最后的null可以省略）
规律4:val 为 null 的节点，没有子节点

思路：

创建节点
挂载节点【挂载节点关键在于找父节点，父节点为非null的节点，与节点创建的顺序一致。】
1. index===0
2. index 为奇数，当前节点挂载到左边
3. index 为非0偶数，当前节点挂载到右边，【父节点出队】
节点入队

测试用例（数组构建二叉树）：

//getBinaryTreeFromArray.test.ts

test("getBinaryTreeFromArray", () => {
  const tree1 = getBinaryTreeFromArray([]);
  expect(tree1).toBe(null);

  const tree2 = getBinaryTreeFromArray([1, 2, 3]);
  expect(tree2.val).toBe(1);
  expect(tree2.left.val).toBe(2);
  expect(tree2.right.val).toBe(3);

  const tree3 = getBinaryTreeFromArray([1, null, 2, 3]);
  expect(tree3.val).toBe(1);
  expect(tree3.right.val).toBe(2);
  expect(tree3.right.left.val).toBe(3);

  const tree4 = getBinaryTreeFromArray([
    5,
    4,
    7,
    3,
    null,
    2,
    null,
    -1,
    null,
    9
  ]);
  expect(tree4.val).toBe(5);
  expect(tree4.left.val).toBe(4);
  expect(tree4.left.left.val).toBe(3);
  expect(tree4.left.left.left.val).toBe(-1);
  expect(tree4.right.val).toBe(7);
  expect(tree4.right.left.val).toBe(2);
  expect(tree4.right.left.left.val).toBe(9);
});

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
26
27
28
29
30
31
32
33
34
35
36
37

步骤：

创建文件 getBinaryTreeFromArray.ts
实现函数基本结构
创建文件 getBinaryTreeFromArray.test.ts
粘贴测试用例代码

# 3-3 二叉树层序遍历-通过数组构建二叉树-实现

问题：

如何通过数组构建二叉树

分析：

创建节点
挂载节点【挂载节点关键在于找父节点，父节点为val为非null的节点，与节点创建的顺序一致。】
1. index===0
2. index 为奇数，当前节点挂载到左边
3. index 为非0偶数，当前节点挂载到右边，【父节点出队】
节点入队【父节点队列】

步骤：

打开 getBinaryTreeFromArray.ts
准备变量 arrIndex,tree,queue
遍历数组
1. 根据数组元素创建树节点
2. 挂载节点
  1. 当前节点为根节点时
  2. 当前节点为奇数节点时
  3. 当前节点为非零偶数节点时,父节点出队
3. 节点入队
返回 tree

扩展：

利用队列实现广度优先搜索（BFS）—— 参考 3-8 节

# 3-4 二叉树层序遍历-二叉树遍历

问题：

来源：leetcode (opens new window)

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3] 1
2 / 3

输出: [1,3,2]

分析：

递归解题思路

递推公式
- f（tree）=f（tree.left）+print(tree.val)+f(tree.right)
终止条件
- Tree 为 null 时终止

测试用例

import getBinaryTreeFromArray from "./getBinaryTreeFromArray";
import inorderTraversal from "./inorderTraversal";

test("inorderTraversal", () => {
  const tree = getBinaryTreeFromArray([1, null, 2, 3]);

  expect(tree.val).toBe(1);
  expect(tree.right.val).toBe(2);
  expect(tree.right.left.val).toBe(3);

  const expectResult = [1, 3, 2];

  const result = inorderTraversal(tree);
  expect(JSON.stringify(result)).toBe(JSON.stringify(expectResult));
});

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

步骤：

创建文件 inorderTraversal
1. 创建文件 inorderTraversal.ts
2. 编写函数结构
3. 导出
编写测试用例
1. 创建文件 inorderTraversal.test.ts
2. 粘贴测试用例
完善细节
1. 声明 result 变量
2. 实现 traversal 函数
  1. 处理节点为空的情况
  2. 遍历左子树
  3. 将当前节点的值 push 到 result
  4. 遍历右子树
3. 调用 traversal 函数
4. 返回 result
优化 getBinaryTreeFromArray

所有的测试都无法做到100%，只有不断的迭代才能提高软件质量。算法也是如此！

# 3-5 二叉树层序遍历-解题

问题：

二叉树的层序遍历

分析：

如果遍历树的时候知道当前节点的层级就好了！

测试用例：

// 给定二叉树: [3,9,20,null,null,15,7],

//     3
//    / \
//   9  20
//     /  \
//    15   7
// 返回其层次遍历结果：

// [
//   [3],
//   [9,20],
//   [15,7]
// ]

import getBinaryTreeFromArray from "./getBinaryTreeFromArray";
import layerTraversal from "./layerTraversal";

test("layerTraversal", () => {
  const tree = getBinaryTreeFromArray([3, 9, 20, null, null, 15, 7]);

  expect(tree.val).toBe(3);
  expect(tree.left.val).toBe(9);
  expect(tree.right.val).toBe(20);
  expect(tree.right.left.val).toBe(15);
  expect(tree.right.right.val).toBe(7);

  const expectResult = [[3], [9, 20], [15, 7]];

  const result = layerTraversal(tree);
  expect(JSON.stringify(result)).toBe(JSON.stringify(expectResult));
});

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
26
27
28
29
30
31
32

解决：

实现函数主体结构
1. 创建文件 layerTraversal.ts
2. 粘贴 inorderTraversal 代码
3. 修改函数名称
实现测试用例
1. 创建文件
2. 粘贴代码
完善函数细节
1. 给 traversal 添加可选参数层级 deepth=0
2. 调用 traversal 时添加将 tree.val 添加到层级数组中 result[deepth]
  1. 层级数组为空，添加数组
  2. 层级数组不为空，push(val)

# 3-6 N叉树的层序遍历-读题

题目：

来源：leetcode (opens new window)

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

示例：

给定一个 3叉树 :

返回其层序遍历:

[ [1], [3,2,4], [5,6] ]

准备工作：

多叉树节点表示：

//MultiwayTreeNode.ts
class MultiwayTreeNode<T> {
  val: T;
  children: MultiwayTreeNode<T>[];
  constructor(val: T, children: MultiwayTreeNode<T>[] = []) {
    this.val = val;
    this.children = children;
  }
}

export default MultiwayTreeNode;

1
2
3
4
5
6
7
8
9
10
11

layerTraversalForMultiwayTree 框架代码：

//layerTraversalForMultiwayTree.ts
import MultiwayTreeNode from "./MultiwayTreeNode";

const layerTraversalForMultiwayTree = (root: MultiwayTreeNode<number>) => {
  const result = [];

  return result;
};

export default layerTraversalForMultiwayTree;

1
2
3
4
5
6
7
8
9
10

测试用例：

//layerTraversalForMultiwayTree.test.ts

import MultiwayTreeNode from "./MultiwayTreeNode";
import layerTraversalForMultiwayTree from "./layerTraversalForMultiwayTree";

test("layerTraversalForMultiwayTree", () => {
  /**
   *
   *       1
   *    /  ｜  \
   *   3   2    4
   *  / \
   * 5   6
   *
   */

  const node1 = new MultiwayTreeNode<number>(1, []);
  const node2 = new MultiwayTreeNode<number>(2, []);
  const node3 = new MultiwayTreeNode<number>(3, []);
  const node4 = new MultiwayTreeNode<number>(4, []);
  const node5 = new MultiwayTreeNode<number>(5, []);
  const node6 = new MultiwayTreeNode<number>(6, []);
  const tree = node1;
  tree.children = [node3, node2, node4];
  node3.children = [node5, node6];

  const result = [[1], [3, 2, 4], [5, 6]];

  expect(JSON.stringify(layerTraversalForMultiwayTree(tree))).toBe(
    JSON.stringify(result)
  );
});

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
26
27
28
29
30
31
32

# 3-7 N叉树的层序遍历-递归解

问题：

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

分析：

直接参考二叉树的层序遍历逻辑

把中序遍历改成前序遍历
递归2个子节点改成递归多个子节点

步骤：

打开文件 layerTraversalForMultiwayTree.ts
将 layerTraversal 的函数主体拷贝到 layerTraversalForMultiwayTree.ts
中序遍历改成前序遍历
将【递归2个子节点】改成【递归多个子节点】
测试

# 3-8 N叉树的层序遍历-bfs解

问题：

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

bfs= breadth first search 广度优先搜索算法

分析：

实现 bfs：

将根节点推入到一个队列中
针对队列中的节点逐个执行以下操作
1. 出队一个元素 item
2. 讲 item 的值 push到 result 中
3. item 的子节点逐个入队

加入深度信息：

优化— — 加入深度信息
1. 在队列的 item 中添加深度信息【深度信息与树的节点一同入队】

步骤：

准备工作
1. 创建文件 breadthFirstSearch.ts
2. 完成函数的主体结构并导出
3. 在 layerTraversalForMultiwaryTree.test.ts 添加相应的测试用例
非核心逻辑
1. 编写队列 item 类型 QueueItem={depth,tree}
2. 定义变量 result=[] 并返回 result
3. 处理空树的情况
4. 定义变量 queue = new Queue();
5. 实现 pushResult 方法— 根据 deepth 把 val 放入正确的位置
核心逻辑
1. 根节点（携带深度信息）入队
2. 逐个处理队列中的节点
  1. 获取 tree 和 deepth 信息
  2. 调用 pushResult
  3. 逐个将子元素（携带深度信息）入队—— 注意 deepth+1

# 3-9 N叉树的层序遍历-dfs解

问题：

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

dfs= depth first search 深度优先搜索算法

分析：

将广度优先搜索算法改成深度优先搜索算法即可！

复用 bfs 代码
将队列换成栈
子元素倒序入栈

步骤：

添加文件 depthFirstSearch.ts
复制 breadthFirstSearch.ts 到 depthFirstSearch.ts，修改函数名和导出
在 layerTraversalForMultiwaryTree.test.ts 添加相应的测试用例
将队列改为栈
子节点入栈前先倒序
测试

← 第2章线性结构算法题第4章综合算法题 →

# 第3章 非线性结构算法题

# 3-1 二叉树层序遍历-读题

# 3-2 二叉树层序遍历-通过数组构建二叉树-思路

# 3-3 二叉树层序遍历-通过数组构建二叉树-实现

# 3-4 二叉树层序遍历-二叉树遍历

# 3-5 二叉树层序遍历-解题

# 3-6 N叉树的层序遍历-读题

# 3-7 N叉树的层序遍历-递归解

# 3-8 N叉树的层序遍历-bfs解

# 3-9 N叉树的层序遍历-dfs解

# 第3章非线性结构算法题