# 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/)


---

# 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://junnie.gitbook.io/nine-chapter/2.binary-tree/145.-binary-tree-postorder-traversal-e.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.