第8章数据结构之“树”.md · pleaseAnswer/algorithm

# 数据结构之“树”

## 一、理论

### 1. 树简介

* 树是一种 __分层__ 数据的抽象模型
* 常见树：DOM树、级联选择、树形控件...
* js中没有树，但可以用Object和Array构建树
* 树的常用操作：深度/广度优先遍历、先中后序遍历

### 2. 深度/广度优先遍历

```js
const tree = {
  val: 'a',
  children: [{
    val: 'b',
    children: [{
      val: 'd',
      children: [],
    },{
      val: 'e',
      children: [],
    }],
  },{
    val: 'c',
    children: [{
      val: 'f',
      children: [],
    },{
      val: 'g',
      children: [],
    }],
  }],
}
```

* 深度优先遍历：尽可能深的搜索树的分支
* 广度优先遍历：先访问离根节点最近的节点

#### 2.1 深度优先遍历

* 递归

##### 2.1.1 算法口诀

1. 访问根节点
2. 对根节点的children挨个进行深度优先遍历

##### 2.1.2 coding part

```js
// dfs
const DFS = root => {
  console.log(root.val)
  root.chileren.forEach(child => DFS(child))
}
// abdecfg
```

#### 2.2 广度优先遍历

* 队列

##### 2.1.1 算法口诀

1. 新建队列，将根节点入队
2. 队头出队并访问
3. 把队头的children挨个入队
4. 重复2 3 直到队列为空

##### 2.1.2 coding part

```js
// bfs
const BFS = root => {
  const q = [root]
  while(q.length) {
    const n = q.shift()
    console.log(n.val)
    n.children.forEach(child => q.push(child))
  }
}
// abcdefg
```

### 3. 二叉树的先中后序遍历（递归）

#### 3.1 什么是二叉树

```js
// bt
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
    }
  }
}
```

* 树中每个节点最多只能有两个子节点
* js中通常用Object模拟二叉树

#### 3.2 先序遍历

##### 3.2.1 先序遍历算法口诀

1. 访问根节点
2. 对根节点的左子树进行先序遍历
3. 对根节点的右子树进行先序遍历

##### 3.2.2 coding part

```js
// preorder
const preorder = root => {
  if(!root) return
  console.log(root.val)
  preorder(root.left)
  preorder(root.right)
}
```

#### 3.3 中序遍历

##### 3.3.1 中序遍历算法口诀

1. 对根节点的左子树进行中序遍历
2. 访问根节点
3. 对根节点的右子树进行中序遍历

##### 3.3.2 coding part

```js
// inorder
const inorder = root => {
  if(!root) return
  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
}
```

#### 3.4 后序遍历

##### 3.4.1 后序遍历算法口诀

1. 对根节点的左子树进行中序遍历
2. 对根节点的右子树进行中序遍历
3. 访问根节点

##### 3.4.2 coding part

```js
// postorder
const postorder = root => {
  if(!root) return
  postorder(root.left)
  postorder(root.right)
  console.log(root.val)
}
```

### 4. 二叉树的先中后序遍历（非递归）

* 堆栈

#### 4.1 先序遍历

##### coding part

```js
// preorder
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)
  }
}
```

#### 4.2 中序遍历

##### coding part

```js
// inorder
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
  }
}
```

#### 4.3 后序遍历

##### coding part

```js
// postorder
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)
  }
}
```

## 二、刷题

### 1. 二叉树的最大深度（104）

#### 1.1 题目描述

* 给定一个二叉树，找出其最大深度
* 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
* 说明: 叶子节点是指没有子节点的节点

#### 1.2 解题思路

* 求最大深度，考虑深度优先遍历
* 在深度优先遍历过程中，记录每个节点所在层级，找出最大的层级即可

#### 1.3 解题步骤

* 新建变量纪录最大深度
* 深度优先遍历整棵树并记录每个节点的层级，不断刷新最大深度
* 遍历结束返回最大深度

```js
function maxDepth(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
}
```

#### 1.4 时间复杂度&空间复杂度

* 时间复杂度：O(n)
* 空间复杂度：O(logn)~O(n)

### 2. 二叉树的最小深度（111）

#### 2.1 题目描述

* 给定一个二叉树，找出其最小深度
* 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
* 说明：叶子节点是指没有子节点的节点

#### 2.2 解题思路

* 求最小深度，考虑广度优先遍历
* 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级

#### 2.3 解题步骤

* 广度优先遍历整棵树并记录每个节点的层级
* 遇到叶子节点，返回节点层级，停止遍历

```js
function minDepth(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])
  }
}
```

#### 2.4 时间复杂度&空间复杂度

* 时间复杂度：O(n)
* 空间复杂度：O(n)

### 3. 二叉树的层序遍历（102）

#### 3.1 题目描述

* 给你二叉树的根节点 root ，返回其节点值的 层序遍历 
* 即逐层地，从左到右访问所有节点

#### 3.2 解题思路

> 输入：root = [3,9,20,null,null,15,7]
> 输出：[ [3],[9,20],[15,7] ]

* 层序遍历顺序就是广度优先遍历
* 遍历时要记录各节点的层级

#### 3.3 解题步骤

* 广度优先遍历
* 遍历时要记录各节点的层级

```js
function levelOrder(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
}
```

##### 方法二

```js
function levelOrder(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
}
```

#### 3.4 时间复杂度&空间复杂度

* 时间复杂度：O(n)
* 空间复杂度：O(n)

### 4. 二叉树的中序遍历（94）

#### 4.1 题目描述

* 给定一个二叉树的根节点 root ，返回它的中序遍历
* 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

#### 4.2 解题

```js
function inorderTraversal(root) {
  const res = []
  const rec = n => {
    if(!n) return
    rec(n.left)
    res.push(n.val)
    rec(n.right)
  }
  rec(root)
  return res
}
```

##### 方法二

```js
function inorderTraversal(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
}
```

#### 4.3 时间复杂度&空间复杂度

* 时间复杂度：O(n)
* 空间复杂度：O(n)

### 5. 路径总和（112）

#### 5.1 题目描述

* 给定二叉树和一个目标和的
* 判断该树中是否存在 __根节点到叶子节点__ 的路径，这条路径上所有节点值相加等于目标和
* 如果存在，返回 true ；否则，返回 false

#### 5.2 解题思路

> 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
> 输出：true

* 深度优先遍历过程中，记录当前路径节点值和
* 叶子节点处，判断当前路径的节点值和是否=目标和

#### 5.3 解题步骤

* 深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值和是否=目标和，是则返回true
* 遍历结束，若没有匹配，则返回false

```js
function hasPathSum(root, sum) {
  if(!root) return false
  let res = false
  const dfs = (n, s) => {
    if(!n.left && !n.right && s === sum) {
      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
}
```

##### 方法二

#### 5.4 时间复杂度&空间复杂度

* 时间复杂度：O(n)
* 空间复杂度：O(logn)~O(n)

### 6 遍历json的所有节点值（前端与树）

```json
const json = {
  a: { b: { c: 1 } },
  d: [1, 2]
}
```

#### 6.1 coding part

```js
const dfs = (n, path) => {
  console.log(n, path)
  Object.keys(n).forEach(k => {
    dfs(n[k], path.concat(k))
  })
}
```

## 三、总结 -- 技术要点

* 树是一种 __分层__ 数据的抽象模型，在前端广泛应用
* 树的常用操作：深度/广度优先遍历、先中后序遍历

pleaseAnswer/algorithm

简介

发行版

贡献者

近期动态

pleaseAnswer/algorithm .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

pleaseAnswer/algorithm