题目描述

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

示例：

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

输出: [3,2,1]

思路

1.后续遍历是左->右->根，可以借助栈将顺序改为根->右->左（方便处理，可以参考前序遍历），然后逆序输出即可。

Java代码实现

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();

        Stack<TreeNode> stack = new Stack();

        if(root != null)
            stack.push(root);

        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();

            res.add(0,cur.val);

            if(cur.left != null)
                stack.push(cur.left);

            if(cur.right != null)
                stack.push(cur.right);
        }

        return res;
    }