> For the complete documentation index, see [llms.txt](https://coffe1891.gitbook.io/frontend-hard-mode-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coffe1891.gitbook.io/frontend-hard-mode-interview/id-2/1.-mian-shi-shi-gao-pinlchu-xian-de-suan-fa/2.1.4.md).

# 贰.1.4 二叉树的遍历

对于给定的二叉树如图：

![](http://img.blog.csdn.net/20150204101904649?%3C/p%3E%3Cp%3Ewatermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXlfSm9icw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)

## 贰.1.4.1 前序遍历

### 定义

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

文首的图，前序遍历的结果是：12457836

### 题目

给定一个二叉树，返回它的 前序 遍历。示例:

输入: \[1,null,2,3]的树\
`1 \ 2 / 3`\
输出: \[1,2,3]

### 代码

递归解法：

```javascript
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let result=[];
    (function func(root){
        if(root)
            result.push(root.val);    
        if(root&&root.left){
            func(root.left);//递归
        }
        if(root&&root.right){
            func(root.right);//递归
        }
    })(root);
    return result;
};
```

迭代解法：

```javascript
/**
 * @param {TreeNode} root
 * @return {arr[]}
 */
var preorderTraversal = function (root) {
    let stack = [root];
    let arr = [];
    while (stack.length > 0) {//循环迭代
        let node = stack.pop();
        node && arr.push(node.val); // node不为空时，向arr中推入节点值
        node && node.right && stack.push(node.right); //关键点：模拟栈，后入先出，故先压右节点
        node && node.left && stack.push(node.left); // 关键点：后入先出，后压左节点
    }
    return arr
};
```

## 贰.1.4.2 中序遍历

### 定义

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

文首的图，中序遍历的结果是：42758136

### 题目

//略

## 贰.1.4.3 后序遍历

### 定义

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

文首的图，后序遍历的结果是：47852631

### 题目

//略

## 贰.1.4.4 层序遍历

文首的图，层序遍历的结果是：12345678

### 题目

文首的二叉树，请你返回其按 **层序遍历** 得到的节点值（即逐层地，从左到右访问所有节点）。\
返回其层次遍历结果数组：\
`[[1],[2,3],[4,5,6],[7,8]]`

### 思路

利用队列这个数据结构，将每层的节点放进队列，遍历完当前层的节点之后，再将子节点放到队列进行遍历，直到遍历完所有叶节点。

### 代码

```javascript
//用一个多维数组表示树
let tree=[[1,]];

((T)=>{
    let queue=[];
    //todo
    
})(tree);
```

## 贰.1.4.5 深度优先与广度优先遍历

其实深度优先遍历也就是前序遍历，广度优先遍历就是层序遍历。