# 后序遍历|博客系列

> 本文详细讲解了二叉树后序遍历的原理、递归与非递归实现方法，并配有图解和代码示例，帮助读者全面理解后序遍历的实现思路及其在数据结构中的应用。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/5-%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

### 后序遍历

遍历顺序为：

![img2](https://hexo-blog-1256114407.cos.ap-shenzhen-fsi.myqcloud.com/binaryTree2.png)

遍历之后：`["LL","LR","L","RL","RR","R","Root"]`

**递归遍历**

```javascript
function inOrderRec (tree) {
    let list = []
    let inOrderRecFn = function (node) {
        if (node) {
            if (node.left) inOrderRecFn(node.left)
            if (node.right) inOrderRecFn(node.right)
            list.push(node.value)
        }
    }
    inOrderRecFn(tree)
    return list
}
```

**非递归遍历**

非递归遍历的思路是：

1. 通过一个对象`tmp`来记录上一次入栈、出栈的节点；
2. 把根节点和左子树推入栈；
3. 取出左子树的值；
4. 推入右子树，取出右子树的值；
5. 最后取出根节点的值

```javascript
function postOrderUnRec (tree) {
    let list = []
    let postOrderUnRecFn = function (node) {
        if (node) { // 当前节点存在
            let stack = [node] // 将当前节点推入栈
            let tmp = null // 定义一个空的对象用于盛放上一次入栈、出栈的节点
            while(stack.length !== 0) { // 判断条件为 stack 不为空
                tmp = stack[stack.length - 1] // 保存住栈顶的值
                if (tmp.left && tmp.left !== node && tmp.right !== node) { // 若栈顶的值存在左子树且当前的节点不为左子树和右子树节点
                    stack.push(tmp.left) // 将左子树推入栈中
                } else if (tmp.right && tmp.right !== node) {
                    stack.push(tmp.right)
                } else { // 左子树和右子树都遍历完了之后
                    list.push(stack.pop().value)
                    node = tmp
                }
            }
        }
    }
    postOrderUnRecFn(tree)
    return list
}
```
