# 后序遍历

后序遍历的顺序是`左右根`

## 递归实现

```javascript
const postOrder = function (root, array = []) {
  if (root) {
    postOrder(root.left, array);
    postOrder(root.right, array);
    array.push(root.val);
  }
  return array;
};
```

## 非递归实现

* 取跟节点为目标节点，开始遍历
* 1.左孩子入栈 -> 直至左孩子为空的节点
* 2.栈顶节点的右节点为空或右节点被访问过 -> 节点出栈并访问他，将节点标记为已访问
* 3.栈顶节点的右节点不为空且未被访问，以右孩子为目标节点，再依次执行1、2、3

```javascript
const postOrder = function (root) {
  const result = [];
  const stack = [];
  let last = null; // 标记上一个访问的节点
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack[stack.length - 1];
    if (!current.right || current.right == last) {
      current = stack.pop();
      result.push(current.val);
      last = current;
      current = null; // 继续弹栈
    } else {
      current = current.right;
    }
  }
  return result;
}
```

## 更好的实现，双栈

```javascript
/**
 * 后序遍历
 * 非递归方式
 *
 * 双栈，一个栈用来按顺序记录左右孩子，一个栈用来弹栈输出结果
 * @param {树} root
 */
export function backNoRecursive(root) {
  const result = [];
  const stack1 = [];
  const stack2 = [];
  let current = root;
  stack1.push(current);
  while (current || stack1.length > 0) {
    current = stack1.pop();
    stack2.push(current);
    if (current.left) stack1.push(current.left);
    if (current.right) stack1.push(current.right);
  }
  while (stack2.length > 0) {
    result.push(stack2.pop());
  }
  return result;
}
```


---

# 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://mm.ricky.moe/algorithm/algorithm-and-data-structure/er-cha-shu-zhuan-ti/hou-xu-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.