后序遍历递归和非递归-Java-LeetCode145

    //后序遍历非递归：比中序遍历多一个记录节点last，用于记录上一次返回的是不是从right节点返回。
    public List<Integer> postorderTraversal_1(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if(root == null)
            return ans;
        TreeNode cur = root;
        TreeNode last = null;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.empty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.peek();
                if(cur.right != null && cur.right != last){
                    cur = cur.right;
                }else{
                    last = cur;
                    ans.add(cur.val);
                    stack.pop();
                    cur = null;
                }
            }
        }
        return ans;
    }

    //后序遍历非递归：使用了先序遍历的知识，先序遍历是根->左->右，后序遍历是左->右->根，对于list的添加顺序可以变成在队列头添加（根->右->左），这样队列添加完就是左->右->根的顺序了。
    public List<Integer> postorderTraversal_2(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if(root == null)
            return ans;
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(cur);
        while(!stack.empty()){
            cur = stack.pop();
            if(cur.left != null){
                stack.add(cur.left);
            }
            if(cur.right != null){
                stack.add(cur.right);
            }
            ans.add(0, cur.val);
        }
        return ans;
    }



    //后序遍历递归
    public List<Integer> postorderTraversal_3(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if(root == null)
            return ans;
        subPostorderTraversal(root, ans);
        return ans;
    }
    private void subPostorderTraversal(TreeNode root, List<Integer> ans){
        if(root == null)
            return;
        subPostorderTraversal(root.left, ans);
        subPostorderTraversal(root.right, ans);
        ans.add(root.val);
    }