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

矫情吗；* 2022-05-09 05:44 135阅读 0赞

难易程度：★★

重要性：★★★★★

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

/**
         * 后序遍历 非递归
         * 
         * 后序遍历顺序：左右根 -> 变换：先获得根右左的遍历顺序，再反转（ 根右左的顺序可以通过栈即可实现）
         * 
         * @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、大数据项目**，**资料很全，你想找的几乎都有**

![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）

**推荐阅读**

[1240]: /images/20220509/a5abb28fdc8845ffb8119dbce749e5c1.png