29.二叉树的后序遍历

题目描述

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

解题思路

递归

递归方法很简单，不再赘述。

Code：

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return ans;
        }
        if(root.left != null){
            postorderTraversal(root.left);
        }
        if(root.right != null){
            postorderTraversal(root.right);
        }
        ans.add(root.val);
        return ans;
    }
}

迭代

迭代的方式时间复杂度与空间复杂度与递归一样，区别在于递归的时候隐式地维护了一个栈，迭代的时候需要显式地讲这个栈模拟出来，其余的实现与细节都相同。

Code：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}