> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/91-days-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/91-days-algorithm/medium/hot/34.traversal-of-binary-tree.md).

# 34.traversal-of-binary-tree

## 二叉树遍历系列

[144.二叉树的前序遍历](https://suki.gitbook.io/91-days-algorithm/medium/hot/pages/-MNgQjuxfp7u0PyxDmjT#144.二叉树的前序遍历)

[94.二叉树的中序遍历](https://suki.gitbook.io/91-days-algorithm/medium/hot/pages/-MNgQjuxfp7u0PyxDmjT#94.二叉树的中序遍历)

[145.二叉树的后序遍历](https://suki.gitbook.io/91-days-algorithm/medium/hot/pages/-MNgQjuxfp7u0PyxDmjT#145.二叉树的后序遍历)

[102.二叉树的层序遍历](https://suki.gitbook.io/91-days-algorithm/medium/hot/pages/-MNgQjuxfp7u0PyxDmjT#102.二叉树的层序遍历)

**扩展**

* 多叉树的遍历，参考[图的遍历](https://github.com/suukii/Articles/blob/master/articles/dsa/dsa_graph.md#%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86)
* $O(1)$ 空间的遍历，[Morris Traversal](https://github.com/suukii/Articles/blob/master/articles/dsa/dsa_binary_tree.md#morris-traversal)

## 144.二叉树的前序遍历

### 递归

#### 思路

1. 首先打印 `root`
2. 然后遍历左子树的所有节点
3. 再遍历右子树的所有节点

> 在遍历顺序中，根节点是在**最前面**的，所以叫做**前序遍历**。

```
print(root)
preorder(root.left)
preorder(root.right)
```

#### 复杂度分析

* 时间复杂度：$O(2^h)$，h 为二叉树的高度。也可以表示为 $O(n)$，n 为二叉树的节点数。
* 空间复杂度：$O(h)$，h 为二叉树的高度。

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root, res = []) {
    if (!root) return [];

    res.push(root.val);
    root.left && preorderTraversal(root.left, res);
    root.right && preorderTraversal(root.right, res);
    return res;
};
```

### 迭代

#### 思路

1. 使用一个栈来实现 DFS，首先把 root 入栈，
2. 当栈不为空时，弹出栈顶元素 node，然后把 node 的左右节点分别入栈，接着把 node 的值存到结果数组 res，
3. 当栈为空时遍历结束。

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    const stack = [root];
    const res = [];

    while (stack.length > 0) {
        const node = stack.pop();
        if (node) {
            res.push(node.val);
            stack.push(node.right, node.left);
        }
    }
    return res;
};
```

## 94.二叉树的中序遍历

### 递归

#### 思路

1. 首先遍历左子树的所有节点
2. 打印 `root`
3. 再遍历右子树的所有节点

> 在遍历顺序中，根节点是在**中间**的，所以叫做**中序遍历**。

```
inorder(root.left)
print(root)
inorder(root.right)
```

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root, res = []) {
    if (!root) return [];
    root.left && inorderTraversal(root.left, res);
    res.push(root.val);
    root.right && inorderTraversal(root.right, res);
    return res;
};
```

### 迭代

#### 思路

1. 二叉树的中序遍历是 left -> root -> right
2. 我们从 root 开始遍历，把 root 入栈，然后 root.left 入栈，然后 root.left.left 入栈，...，直到遍历到最深层的叶子左节点
3. 开始将栈顶元素弹出，如果该元素没有右子节点，说明这是个左子节点，直接放入 res 数组，
4. 如果该元素有右子节点，说明这还是这个父节点，把父节点放入 res 数组，然后把它的右子节点当成新的 root 重复步骤 2-4。

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    const stack = [];
    const res = [];

    while (root || stack.length > 0) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};
```

## 145.二叉树的后序遍历

### 递归

#### 思路

1. 首先遍历左子树的所有节点
2. 然后遍历右子树的所有节点
3. 最后打印 `root`

> 在遍历顺序中，根节点是在**最后面**的，所以叫做**后序遍历**。

```
postorder(root.left)
postorder(root.right)
print(root)
```

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root, res = []) {
    if (!root) return [];

    root.left && postorderTraversal(root.left, res);
    root.right && postorderTraversal(root.right, res);
    res.push(root.val);

    return res;
};
```

### 迭代

#### 思路 1

这是比较讨巧的思路。

1. 二叉树的前序遍历是 root -> left -> right
2. 二叉树的后序遍历是 left -> right -> root
3. 可以看到后序遍历差不多是前序遍历的结果倒转过来，我们可以把前序遍历的套路拿过来稍做改动。
4. 只需把第 2 步把 node 存入 res 这一步由 `res.push(node.val)` 改为 `res.unshift(node.val)`，并且将左右子节点入栈的顺序调换一下即可。

#### 代码 1

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    const stack = [root];
    const res = [];
    while (stack.length > 0) {
        const node = stack.pop();
        if (node) {
            stack.push(node.left, node.right);
            res.unshift(node.val);
        }
    }
    return res;
};
```

#### 思路 2

这是比较正经的思路。

因为后序遍历的顺序是 left -> right -> root，我们需要先遍历 left，但如果直接遍历，访问完 left 之后没办法回到 root 了，因为二叉树的子节点是没有指向父节点的指针的。

所以，在遍历 left 之前，我们需要把 root 和 right 存起来，访问完 left 之后再回到 root，这时候需要判断，如果 root.right 存在且还没访问过，就先去访问 root.right，否则直接打印 root 的值。

1. 将 root.right 和 root 入栈，稍后遍历。
2. 让 `root = root.left` (相当于将 root 看成一个 cur 指针)。
3. 当 root 不为空时，重复步骤 1 和 2。
4. 开始出栈，`root = stack.pop()`，检查 root.right 有没有被访问过：
   1. 如果没有被访问过的话，这时候 root.right 应该在栈顶，将 root.right 弹出，然后将 root 压回栈等最后再遍历。接着让 `root = root.right`，开始处理右子树。
   2. 如果已经被访问过，或者 root.right 为空的话，这时我们直接打印 root 的值就好了。

#### 代码 2

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    if (!root) return [];

    const stack = [];
    const res = [];

    while (true) {
        while (root) {
            root.right && stack.push(root.right);
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();

        if (root.right && root.right === stack[stack.length - 1]) {
            const right = stack.pop();
            stack.push(root);
            root = right;
        } else {
            res.push(root.val);
            root = null;
        }

        if (!stack.length) break;
    }

    return res;
};
```

## 102.二叉树的层序遍历

### 迭代

#### 思路

1. 可以利用一个队列来简化遍历操作，首先将根节点入列；
2. 接着开始出列，再分别把出列节点的左右子节点入列，重复这一步的操作直到所有节点都被遍历了；
3. 问题是，如何识别当前行是否已经遍历完成？我们可以使用一个特殊标识符(比如 `null`)；
4. 在将根节点入列后，马上入列一个 `null` 作为第一行的结束标识；
5. 接着根节点出列，根节点的左右子节点入列；接着 `null` 出列，说明第一行已经遍历结束，这时候队列里的都是第二行的节点，此时我们再入列一个 `null` 作为第二行的结束标识，再次开始出列，重复这个操作直到队列为空；
6. 注意，我们入列 `null` 的时候要先判断队列当前是否为空，如果队列为空就不要入列了，不然会无限循环的。

**关键点**

1. 用一个特殊标识符 `null` 来表示每一行的末尾；
2. 如果不想使用特殊标识符，可以在遍历每一行之前记录队列当前的长度，参考下方的 Python Code。

#### 复杂度分析

* 时间复杂度：$O(n)$，n 为树的节点数。
* 空间复杂度：$O(2^h)$，h 为树的高度，队列的最大长度是最深一层叶子节点的总数 $2^(h-1)$。

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return [];

    const result = [];
    const queue = [root, null];
    let level = 0;

    while (queue.length > 0) {
        const node = queue.shift();

        if (node) {
            result[level] || (result[level] = []);
            result[level].push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        } else {
            queue.length > 0 && queue.push(null);
            level++;
        }
    }
    return result;
};
```

Python Code

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
  def levelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if root == None: return []

    items = []
    queue = [root]
    level = []

    while len(queue) > 0:
      size = len(queue)
      level = []

      for i in range(size):
        node = queue.pop(0)

        if node != None:
          level.append(node.val)
          if node.left != None: queue.append(node.left)
          if node.right != None: queue.append(node.right)

      items.append(level)
    return items
```

### 递归

#### 思路

多加一个变量来标识当前遍历的深度。

#### 复杂度分析

* 时间复杂度：$O(n)$, n 为二叉树的节点数。
* 空间复杂度：$O(n)$, n 为二叉树的节点数，`res` 数组的空间是 $O(n)$，调用栈的空间最大是 $O(h)$，h 是二叉树的深度，因为 $n >= h$，所以最后还是 $O(n)$。

#### 代码

JavaScript Code

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root, depth = 0, res = []) {
    if (!root) return [];

    res[depth] || (res[depth] = []);
    res[depth].push(root.val);

    levelOrder(root.left, depth + 1, res);
    levelOrder(root.right, depth + 1, res);

    return res;
};
```