leetcode145. 二叉树的后序遍历

题目描述

给定一个二叉树，返回它的 后序 遍历。
相关话题： 栈、树    难度： 困难

示例

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

• 解法1
  二叉树的题用递归解法是相当简洁的，后序遍历的话就先处理左子树再处理右子树，最后处理当前节点。
  
  二叉树的递归遍历中，每个节点都会被经历三次（如上图所示），所谓的前中后序遍历其实就看你在哪一次经过当前节点的时候对节点进行操作。

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorderTraversal(res,root);
        return res;
    }
    public void postorderTraversal(List<Integer> res, 
                                    TreeNode root){
        if(root == null) return;
        postorderTraversal(res,root.left);
        postorderTraversal(res,root.right);
        res.add(root.val);
    }

• 解法2
  这道题的难度系数之所以定义为困难，就是需要用迭代的方式来做，就要将递归版本改为用栈记录以前的信息。
  既然是后序遍历，则需要遵循"左子树->右子树->当前节点"的访问顺序。
  思路：后序遍历的非递归版本是三种遍历中最难的。这里我们使用两个栈来协助完成二叉树的遍历操作。
  不难发现，如果我们以“中->右->左”的顺序遍历二叉树，将结果压进栈中，弹栈的时候顺序就是“左->右->中”，也就是后序遍历的结果了。
  而“中->右->左”的遍历顺序和先序遍历很像（先序遍历是“中->左->右”）
• 用stack1协助以“中->右->左”的顺序遍历二叉树，将结果保存到stack2中
• 依次弹出stack2中的元素即为二叉树的后序遍历结果
  所以整个过程就是，弹出stack1栈顶节点(也就是访问当前节点)，并将其压进stack2中，如果当前节点有左子树，压进stack1，如果当前节点有右子树，压进stack1。(根据栈FILO的特点，遍历顺序就是“中->右->左”)，最后将stack2中的元素全部弹出即为结果。

 public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode x = stack1.pop();
            stack2.push(x);
            if(x.left != null){
                stack1.push(x.left);
            }
            if(x.right != null){
                stack1.push(x.right);
            }
        }
        while(!stack2.isEmpty()){
            res.add(stack2.pop().val);
        }
        return res;
    }