二叉树的后序遍历（递归和非递归版本）

难易程度：★★

重要性：★★★★★

树结构是面试中的考察的重点，而树的遍历又是树结构的基础。非递归的前序遍历算法思路可以

/**
     * 后序遍历 非递归
     * 
     * 后序遍历顺序：左右根 -> 变换：先获得根右左的遍历顺序，再反转（ 根右左的顺序可以通过栈即可实现）
     * 
     * @param root
     */
    private static ArrayList<Integer> postOrder(TreeNode root) {
        if(root==null)  return new ArrayList<Integer>();

        // 存储："根右左"的遍历顺序
        Stack<Integer> reverseRes = new Stack<Integer>();

        Stack<TreeNode> s = new Stack<TreeNode>();//辅助栈，保存待遍历的节点
        s.add(root);

        while (!s.isEmpty()) {
            TreeNode tem = s.pop();
            reverseRes.push(tem.val);//存储:"根右左"的遍历顺序,先入"根"节点

         // “右左”的遍历顺序，所以在栈(LIFO)中对应的就是：先进"左"，再进"右"
            if (root.left != null)
                s.push(root.left);
            if (root.right != null)
                s.push(root.right);
        }

        ArrayList<Integer> res = new ArrayList<Integer>();//获得“根左右”的遍历序列
        while (!s.isEmpty()) {
            res.add(reverseRes.pop());
        }
        return res;
    }

/**
     * 后序遍历  递归版本
     * @param root
     * @return
     */
    public static ArrayList<Integer> postOrder(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();

        preOrder(root, res);
        return res;
    }

    private static void postOrder(TreeNode root, ArrayList<Integer> res) {
        if (root == null)
            return;

        preOrder(root.left);
        preOrder(root.right);
        res.add(root.val);
    }```



---
扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：
公众号**`菜鸟名企梦`**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；
公众号**`菜鸟名企梦`**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）](https://img.haomeiwen.com/i14326004/6e2e1a12ac02844d.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)