145. Binary Tree Postorder Traversal (E)

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

Example 1:

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

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

Solution:

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，分别代表回溯算法和动态规划的底层思想。

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

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

Version 4: Non-recursive without stack

https://www.geeksforgeeks.org/postorder-traversal-binary-tree-without-recursion-without-stack/