二叉树的前序遍历（递归和非递归）

Bertha 。 2022-06-06 01:14 216阅读 0赞

上一篇是后续遍历，这一篇记录一下前序遍历，递归代码如下：

ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<Integer> preorderTraversal(TreeNode root) {
            if(root == null)
                return list;
            pre(root);
            return list;
        }
        private void pre(TreeNode root){
            if(root == null)
                return;
            list.add(root.val);
            pre(root.left);
            pre(root.right);
        }

非递归的情况是用一个栈记录当前访问的节点的左右节点，右节点先入栈，左节点后入栈，这样出栈的时候顺序才是正确的。  
非递归代码：

ArrayList<Integer> list = new ArrayList<>();
        public ArrayList<Integer> preorderTraversal(TreeNode root) { 
            if(root == null)
                return list;
            Stack<TreeNode> s = new Stack<>();
            s.push(root);
            while(!s.isEmpty()){
                TreeNode temp = s.pop();
                list.add(temp.val);
                if(temp.right != null){
                    s.push(temp.right);
                }
                if(temp.left != null){
                    s.push(temp.left);
                }
            }
            return list;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树层次建树，前序（递归与非递归）遍历--中序遍历（递归与非递归）-后序遍历-层次遍历

创建一个二叉树创建项目为创建C++项目 1.导包开始前需要写一些导包 define _CRT_SECURE_NO_WARNINGS incl

忘是亡心i/ 2023年09月29日 11:26/ 0 赞/ 71 阅读

相关二叉树的前序遍历(非递归)

二叉树的前序遍历 > 题目描述 : > > 给定一个二叉树，返回它的前序遍历。 > > 示例: > > 输入: \[1,null,2,3\] > 1

Bertha 。/ 2023年05月31日 07:24/ 0 赞/ 60 阅读

相关 Java 二叉树前序遍历（递归/非递归）

Java 二叉树前序遍历（递归/非递归）前序遍历代码实现递归方式非递归方式简介：遍历是对

一时失言乱红尘/ 2023年02月13日 03:42/ 0 赞/ 134 阅读

相关二叉树前序遍历的递归与非递归算法

前几天参加了阿里暑期实习的内推面试，发现自己的数据结构算法基础特别薄弱，比如其中一个问题是中序遍历的递归与非递归算法，我平时看数据结构只知道递归算法，非递归的算法直接被问懵逼了

r囧r小猫/ 2022年09月27日 14:22/ 0 赞/ 171 阅读

相关二叉树的前序遍历（递归和非递归）

上一篇是后续遍历，这一篇记录一下前序遍历，递归代码如下： ArrayList<Integer> list = new ArrayList<>(); p

Bertha 。/ 2022年06月06日 01:14/ 0 赞/ 217 阅读

相关二叉树的后序遍历（递归和非递归）

对于二叉树的后序遍历，最常用的就是递归，代码清晰，如下： ArrayList<Integer> list = new ArrayList<>(); p

川长思鸟来/ 2022年06月06日 01:12/ 0 赞/ 287 阅读

相关二叉树前序遍历（递归以及非递归）

二叉树前序遍历对于一种数据结构而言，我们最常见的就是遍历，那么关于二叉树我们该如何去遍历呢？请看大屏幕。。。。 ![在这里插入图片描述][watermark_t

怼烎@/ 2022年04月24日 07:50/ 0 赞/ 253 阅读

相关非递归、递归遍历二叉树！

树的先、中、后、层序的遍历，需要用到栈结构和队结构。首先来看树本身的定义： typedef char TElemType; typedef struct BiTNod

小鱼儿/ 2022年04月13日 10:29/ 0 赞/ 398 阅读

相关二叉树递归和非递归遍历

二叉树递归和非递归遍历 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

拼搏现实的明天。/ 2021年12月17日 04:07/ 0 赞/ 397 阅读

相关二叉树—前序遍历、中序遍历(非递归)

【转载】https://www.cnblogs.com/bigsai/p/11393609.html 层级遍历 public void cengxu(node t

朱雀/ 2021年09月18日 05:06/ 0 赞/ 455 阅读