算法打卡Day17_leetcode _144. 二叉树的前序遍历

简介: 算法打卡Day17_leetcode _144. 二叉树的前序遍历

Leetcode原题

144. 二叉树的前序遍历

20200401134307494.png20200401134307494.png

思路

上一篇leetcode _94. 二叉树的中序遍历 。这一篇的做法类似。

首先来说一下什么是前序遍历。

前序遍历:就是先遍历跟节点,然后再遍历左子树、右子树

方法一 递归实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer> res = new ArrayList<>();
         Deque<TreeNode> statck =new LinkedList<>();
         accessTree(root,res);
         return res;
    }
  public void accessTree(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
       //递归左中右
         res.add(root.val);
        accessTree(root.left,res);
         accessTree(root.right,res);
    }
}

递归实现通常很简单,但是会让你忽律很多的细节。

方法二 迭代

方法一的递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其他都相同,具体实现可以看下面的代码。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //前序遍历: 中左右
         List<Integer> res =new ArrayList<>();
         Deque<TreeNode> statck =new LinkedList<>();
         while(root!=null || !statck.isEmpty()){
             while(root!= null){
                 //遇到跟节点便加入
                 res.add(root.val);
                 //先添加跟节点
                 statck.push(root);
                 //然后左节点入栈
                 root= root.left;
             }
             //左节点遍历完,出栈
             root = statck.pop();
             //遍历右节点
             root = root.right;
         }
        return res;
    }
}

有兴趣的老爷,还可以关注我的公众号【一起收破烂】,回复【006】获取 最新java面试资料以及简历模型120套哦~

相关文章
|
18天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
21 2
|
25天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
17 2
|
25天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
24天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
24天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
24天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
20 0
|
25天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
12 0
|
25天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
11 0
|
25天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
11 0
|
25天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0