# 0145. 二叉树的后序遍历

### 题目地址(145. 二叉树的后序遍历)

<https://leetcode-cn.com/problems/binary-tree-postorder-traversal/>

### 题目描述

```
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

```

### 前置知识

* 栈
* 递归

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

相比于前序遍历，后续遍历思维上难度要大些，前序遍历是通过一个 stack，首先压入父亲结点，然后弹出父亲结点，并输出它的 value，之后压人其右儿子，左儿子即可。

然而后序遍历结点的访问顺序是：左儿子 -> 右儿子 -> 自己。那么一个结点需要两种情况下才能够输出： 第一，它已经是叶子结点； 第二，它不是叶子结点，但是它的儿子已经输出过。

那么基于此我们只需要记录一下当前输出的结点即可。对于一个新的结点，如果它不是叶子结点，儿子也没有访问，那么就需要将它的右儿子，左儿子压入。 如果它满足输出条件，则输出它，并记录下当前输出结点。输出在 stack 为空时结束。

### 关键点解析

* 二叉树的基本操作（遍历）

  > 不同的遍历算法差异还是蛮大的
* 如果非递归的话利用栈来简化操作
* 如果数据规模不大的话，建议使用递归
* 递归的问题需要注意两点，一个是终止条件，一个如何缩小规模

1. 终止条件，自然是当前这个元素是 null（链表也是一样）
2. 由于二叉树本身就是一个递归结构， 每次处理一个子树其实就是缩小了规模， 难点在于如何合并结果，这里的合并结果其实就是`left.concat(right).concat(mid)`, mid 是一个具体的节点，left 和 right`递归求出即可`

### 代码

代码支持：JS, CPP

JS Code:

```js
/**
 * 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) {
  // 1. Recursive solution

  // if (!root) return [];

  // return postorderTraversal(root.left).concat(postorderTraversal(root.right)).concat(root.val);

  // 2. iterative solutuon

  if (!root) return [];
  const ret = [];
  const stack = [root];
  let p = root; // 标识元素，用来判断节点是否应该出栈

  while (stack.length > 0) {
    const top = stack[stack.length - 1];
    if (
      top.left === p ||
      top.right === p || // 子节点已经遍历过了
      (top.left === null && top.right === null) // 叶子元素
    ) {
      p = stack.pop();
      ret.push(p.val);
    } else {
      if (top.right) {
        stack.push(top.right);
      }
      if (top.left) {
        stack.push(top.left);
      }
    }
  }

  return ret;
};
```

CPP Code:

```cpp
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> s;
        TreeNode *prev = NULL;
        while (root || s.size()) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            if (!root->right || root->right == prev) {
                ans.push_back(root->val);
                s.pop();
                prev = root;
                root = NULL;
            } else root = root->right;
        }
        return ans;
    }
};
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

### 相关专题

* [二叉树的遍历](/leetcode-solution/thinkings/binary-tree-traversal.md)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/2b7dwe.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/145.binary-tree-postorder-traversal.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.