二叉树的先序遍历(递归和非递归版本)

末蓝、 2022-05-09 05:22 199阅读 0赞

难易程度：★★

重要性：★★★★★

树结构是面试中的考察的重点，而树的遍历又是树结构的基础。

//先序遍历，递归版本
    public static ArrayList<Integer> preOrder(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<Integer>();
    
            Stack<TreeNode> s = new Stack<TreeNode>();
            s.push(root);
            while (!s.isEmpty()) {
                TreeNode tem = s.pop();// 根节点出栈
    
                // 把根节点加入结果集 前序遍历顺序：根、左，右 所以对应的进栈顺序为：右、左（根节点进栈后马上出栈了）
                res.add(tem.val);
                if (tem.right != null)
                    s.push(tem.right);
                if (tem.left != null)
                    s.push(tem.left);
            }
            return res;
        }
    
    /**
         * 先序遍历，递归版本
         * @param root
         * @return
         */
        public static ArrayList<Integer> preOrder(TreeNode root){
            ArrayList<Integer> res = new ArrayList<Integer>();
    
            preOrder(root,res);
            return res;
        }
        private static void preOrder(TreeNode root,ArrayList<Integer> res) {
            if(root==null)  return;
    
            res.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号**`菜鸟名企梦`**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**

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

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

**推荐阅读**

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