# 二叉树的遍历

##

二叉树的遍历

> 二叉树（Binary Tree）每个节点最多有两个子节点的树型数据结构。

```js
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
```

二叉树的遍历方式主要分为 **深度优先（Deep-first Search, DFS）** 和 **广度优先（Breadth-first Search，BFS）**。

其中深度优先遍历有以下几种方法

1. **前序遍历**
2. **中序遍历**
3. **后序遍历**

### 深度优先

深度优先顾名思义就是先纵向搜索，在进入下一个兄弟节点之前，尽可能的向下搜索每一个子节点。 该算法从根节点开始（在图的情况下选择一些任意节点作为根节点）并在回溯之前尽可能地沿着每个分支进行探索。

#### 前序遍历

前序遍历（pre-order）的访问顺序是 DLR

> L 为左子树，R 为右子树，D 为根节点

![](https://user-gold-cdn.xitu.io/2018/6/20/1641c591b79998b9?imageView2/0/w/1280/h/960/format/webp/ignore-error/1)

上图的前序遍历顺序为: ABDGHCEIF

**前序遍历的递归方式**

```js
function preOrder(root) {
  if (!root) {
    return;
  }
  // do something
  // console.log(root.val)
  preOrder(root.left);
  preOrder(root.right);
}
```

**前序遍历的非递归方式**

对于任一结点 `P`：

1. 访问结点 `P`，并将结点 `P` 入栈;
2. 判断结点 `P` 的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点 `P`，循环至 1; 若不为空，则将 `P` 的左孩子置为当前的结点 `P`;
3. 直到 `P` 为 `null` 并且栈为空，则遍历结束。

```js
function preOrderWithoutRecursion(root) {
  const stack = [];
  let node = root;
  while (node || stack.length > 0) {
    if (node) {
      // do something
      // console.log(node.val);
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop().right;
    }
  }
}
```

#### 中序遍历

中序遍历（in-order）的顺序是 LDR

![](https://user-gold-cdn.xitu.io/2018/6/20/1641c591b78015a9?imageView2/0/w/1280/h/960/format/webp/ignore-error/1)

上图的中序遍历顺序为: GDHBAEICF

**中序遍历的递归方式**

```js
function inOrder(root) {
  if (!root) {
    return;
  }
  inOrder(root.left);
  // do something
  // console.log(root.val);
  inOrder(root.right);
}
```

**中序遍历的非递归方式**

对于任一结点 `P`：

1. 若其左孩子不为空，则将 `P` 入栈并将 `P` 的左孩子置为当前的 `P`，然后对当前结点 `P` 再进行相同的处理；
2. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的 `P` 置为栈顶结点的右孩子；
3. 直到 `P` 为 `null` 并且栈为空则遍历结束

```js
function inOrderWithoutRecursion(root) {
  const stack = [];
  let node = root;
  while (node || stack.length > 0) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      const lastNode = stack.pop();
      // do something
      // console.log(lastNode.val);
      node = lastNode.right;
    }
  }
}
```

#### 后序遍历

后序遍历（post order）的顺序是 LRD

![](https://user-gold-cdn.xitu.io/2018/6/20/1641c591b791e58b?imageView2/0/w/1280/h/960/format/webp/ignore-error/1)

上图的后序遍历顺序为: GHDBIEFCA

**后序遍历的递归方式**

```js
function postOrder(root) {
  if (!root) {
    return;
  }

  postOrder(root.left);
  postOrder(root.right);
  // do something
  // console.log(root.val);
}
```

**后序遍历的非递归方式**

```js
function postOrderWithoutRecursion(root) {
  if (!root) {
    return;
  }
  const stack = [];
  let node = root;
  let last = node;
  stack.push(node);
  while (stack.length > 0) {
    node = stack[stack.length - 1];
    if (
      (!node.left && !node.right) ||
      (!node.right && last === node.left) ||
      last === node.right
    ) {
      // doing something
      // console.log(node.val);
      last = node;
      stack.pop();
    } else {
      if (node.right) {
        stack.push(node.right);
      }
      if (node.left) {
        stack.push(node.left);
      }
    }
  }
}
```

### 广度优先遍历

广度优先遍历，也可以称之为层级遍历，先访问兄弟节点，再访问子节点。

![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Sorted_binary_tree_breadth-first_traversal.svg/220px-Sorted_binary_tree_breadth-first_traversal.svg.png)

上图的后序遍历顺序为: FBGADICEH

```js
function bfs(root) {
  if (!root) {
    return;
  }
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    // do something
    // console.log(node.val)
    if (node.left) {
      queue.push(node.left);
    }
    if (node.right) {
      queue.push(node.right);
    }
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xyy94813.gitbook.io/x-note/ji-chu-suan-fa/er-cha-shu-de-bian-li.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.