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

Bertha 。 2022-06-06 01:14 144阅读 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 条评论，144人围观）

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

相关阅读

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

，中序遍历非递归版本，借助一个辅助 vector<int> ans; vector<int> inorderTraversal(TreeNode* ...

向右看齐/ 2024年04月17日 05:44/ 0 赞/ 11 阅读

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

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

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

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

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

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

相关二叉树先序遍历 -- 递归和非递归实现

/ 实现二叉树先序遍历 -- 采用递归和非递归方法，经调试可直接运行源码如下： / include <stdio.h> include

矫情吗；*/ 2022年07月27日 11:53/ 0 赞/ 133 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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