> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/145.-binary-tree-postorder-traversal-e.md).

# 145. Binary Tree Postorder Traversal (E)

Given the `root` of a binary tree, return *the postorder traversal of its nodes' values*.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/28/pre1.jpg)

```
Input: root = [1,null,2,3]
Output: [3,2,1]
```

**Example 2:**

```
Input: root = []
Output: []
```

**Example 3:**

```
Input: root = [1]
Output: [1]
```

 

**Constraints:**

* The number of the nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`

&#x20;

**Follow up:** Recursive solution is trivial, could you do it iteratively?S

### Solution:

前文 [手把手刷二叉树总结篇](https://labuladong.gitee.io/article/?qno=104) 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，分别代表回溯算法和动态规划的底层思想。

本题用两种思维模式来解答，注意体会其中思维方式的差异。

```java
class Solution {

    Version 1:
    /* 动态规划思路 */
    // 定义：输入一个节点，返回以该节点为根的二叉树的后序遍历结果
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        // 后序遍历结果特点：先是左子树，接着是右子树，最后是根节点的值
        res.addAll(postorderTraversal(root.left));
        res.addAll(postorderTraversal(root.right));
        res.add(root.val);
        return res;
    }
    
    
    Version 2: 

    /* 回溯算法思路 */
    LinkedList<Integer> res = new LinkedList<>();

    // 返回后序遍历结果
    public List<Integer> postorderTraversal2(TreeNode root) {
        traverse(root);
        return res;
    }

    // 二叉树遍历函数
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        traverse(root.right);
        // 后序遍历位置
        res.add(root.val);
    }
}
```

**Version 3: Non-recursive with a stack:**

[**https://app.gitbook.com/s/-M33ghpQv0ZbnP8UX-Qg/\~/changes/0Bt79NwRJ5SlV571DWbq/2.binary-tree/summary/er-cha-shu-ba-gu-wen-di-gui-gai-die-dai**](/nine-chapter/2.binary-tree/summary/er-cha-shu-ba-gu-wen-di-gui-gai-die-dai.md)<br>

**Version 4: Non-recursive without stack**

[**https://www.geeksforgeeks.org/postorder-traversal-binary-tree-without-recursion-without-stack/**](https://www.geeksforgeeks.org/postorder-traversal-binary-tree-without-recursion-without-stack/)