题目描述

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

样例

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

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

算法1

递归

若当前节点不为空，递归把左子树所有结点的值放进ans中，再递归把右子树所有结点的值放进ans中，再将当前节点的值放进ans中

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static List<Integer> ans = new ArrayList<Integer>();
    static void dfs(TreeNode root)
    {
        if(root != null)
        {
            dfs(root.left);
            dfs(root.right);
            ans.add(root.val);
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        ans.clear();
        dfs(root);
        return ans;
    }
}

算法2

迭代

前序遍历的做法如下：

将整课树的最左边一条链压入栈中，并记录当前元素，每次取出栈顶元素，如果它有右子树，则将右子树压入栈中。

后续遍历的做法如下：

• 1、前序遍历的顺序：根，左，右
• 2、可以根据类型前序遍历的思想，遍历出：根，右，左
• 3、再通过 2 中遍历出来的顺序，通过反转得到后序遍历：左，右，根

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        while(p != null || !stk.isEmpty())
        {
            while(p != null)
            {
                ans.add(p.val);
                stk.add(p);
                p = p.right;
            }
            p = stk.pop();
            p = p.left;
        }
        Collections.reverse(ans);
        return ans;
    }
}