二叉树 - 前/中/后序遍历、层次遍历 - 《计算机基础》

一、是什么

在百度百科中，二叉树是这样定义的：
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二、例题

接下来我们来讲讲几种遍历的递归与迭代实现。

1、二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。
示例： :::info 输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3] ::: 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路

递归算法就不多说了，很简单。

var preorderTraversal = function(root) {
    const res = []
    const preOrder = function (root) {
        if (!root) return;
        res.push(root.val)
        preOrder(root.left)
        preOrder(root.right)
    }
    preOrder(root)
    return res
};

当我们采用迭代时，我们可以通过用栈去模拟递归。
由于栈是先入后出的，所以在前序遍历中按照右左中的顺序入栈，这样在取得栈顶元素的过程中，才能按照中左右的顺序去操作。

var preorderTraversal = function(root) {
    const res = []
    if (!root) return res
    const stack = [root] 
    while (stack.length) {
        const node = stack.pop()
        res.push(node.val)
        node.right && stack.push(node.right)
        node.left && stack.push(node.left)
    }
    return res
};

2.二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。 :::info 输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2] :::

思路

具体就不细说了，与前序遍历相似，只是存入根节点的位置发生了改变，顺序为左根右。

递归算法

var inorderTraversal = function(root) {
  const res = []
  const inorder = function(root) {
      if (!root) return;
      inorder(root.left)
      res.push(root.val)
      inorder(root.right)
  }
  inorder(root)
  return res
};

迭代算法

var inorderTraversal = function(root) {
  const res = []
  if (!root) return res
  const stack = [root]
  while (stack.length) {
      const node = stack.pop()
     if (!node) {
         res.push(stack.pop().val)
         continue
     }
      // 存入栈顺序为： 右中左
      node.right && stack.push(node.right)
      stack.push(node)
      stack.push(null)
      node.left && stack.push(node.left)
  }
  return res
};

3.二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。 :::info 输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1] :::

思路

具体就不细说了，与前序遍历相似，只是存入根节点的位置发生了改变，顺序为左右根。

递归

var postorderTraversal = function(root) {
  const res = []
  const postorder = function(root) {
      if (!root) return;
      postorder(root.left)
      postorder(root.right)
      res.push(root.val)
  }
  postorder(root)
  return res
};

迭代

var postorderTraversal = function(root) {
  const res = []
  if (!root) return res
  const stack = [root]
  while (stack.length) {
      const node = stack.pop()
      if (!node) {
          res.push(stack.pop().val)
          continue
      }
      stack.push(node)
      stack.push(null)
      node.right && stack.push(node.right)
      node.left && stack.push(node.left)
  }
  return res
};

4.二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。 ```javascript 二叉树：[3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回其层次遍历结果：

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

<a name="Tf83y"></a>
#### 思路
层序遍历是一道经典题，我们可以通过`DFS`或者`BFS`来解决。
- **DFS（深度优先搜索遍历）**
遍历的时候记录里一下`level`，每次递归都把`level`+1，即可获得正确的层级，`push`到对应的数组即可
```javascript
var levelOrder = function(root) {
    const res = []
    const dfs = function (root, level) {
        if (!root) return;
        // 创建当前层次的数组
        if (!res[level]) {
            res[level] = []
        } 
        // 存入当前层次节点
        res[level].push(root.val)
        // 递归，层次加一
        dfs(root.left, level+1)
        dfs(root.right, level+1)
    }
    dfs(root, 0)
    return res
};

BFS（广度优先搜索遍历）

利用队列先进先出的特性，在遍历到当前节点时，while 中对于每轮的节点开一个 for 循环加入到数组的一层中，将其子节点存入到队列中。

var levelOrder = function(root) {
    const res = []
    if (!root) return res 
    const queue = [root]
    while (queue.length) {
        const len = queue.length
        const level = []
        // 遍历当前层次节点
        for (let i = 0; i < len; i++) {
            const node = queue.shift()
            level.push(node.val)
            // 将当前节点的子节点存入队列
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(level)
    }
    return res
};