树的遍历:迭代 & 递归|Java 刷题打卡

简介: 树的遍历:迭代 & 递归|Java 刷题打卡

题目描述



这是 LeetCode 上的 872. 叶子相似的树


Tag : 「树的搜索」、「非递归」、「递归」、「DFS」


请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。


网络异常,图片无法展示
|


举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。


如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。


如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。

 

示例 1:


网络异常,图片无法展示
|


输入:
root1 = [3,5,1,6,2,9,8,null,null,7,4], 
root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出:true
复制代码


示例 2:


输入:root1 = [1], root2 = [1]
输出:true
复制代码


示例 3:


输入:root1 = [1], root2 = [2]
输出:false
复制代码


示例 4:


输入:root1 = [1,2], root2 = [2,2]
输出:true
复制代码


示例 5:


网络异常,图片无法展示
|


输入:root1 = [1,2,3], root2 = [1,3,2]
输出:false
复制代码


提示:


  • 给定的两棵树可能会有 1 到 200 个结点。
  • 给定的两棵树上的值介于 0 到 200 之间。


递归



递归写法十分简单,属于树的遍历中最简单的实现方式。


代码:


class Solution {
    public boolean leafSimilar(TreeNode t1, TreeNode t2) {
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        dfs(t1, l1);
        dfs(t2, l2);
        if (l1.size() == l2.size()) {
            for (int i = 0; i < l1.size(); i++) {
                if (!l1.get(i).equals(l2.get(i))) return false;
            }
            return true;
        }
        return false;
    }
    void dfs(TreeNode root, List<Integer> list) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        dfs(root.left, list);
        dfs(root.right, list);
    }
}
复制代码


  • 时间复杂度:nm 分别代表两棵树的节点数量。复杂度为 O(n+m)O(n + m)O(n+m)
  • 空间复杂度:nm 分别代表两棵树的节点数量,当两棵树都只有一层的情况,所有的节点值都会被存储在 listlistlist 中。复杂度为 O(n+m)O(n + m)O(n+m)


迭代



迭代其实就是使用「栈」来模拟递归过程,也属于树的遍历中的常见实现形式。


一般简单的面试中如果问到树的遍历,面试官都不会对「递归」解法感到满意,因此掌握「迭代/非递归」写法同样重要。


代码:


class Solution {
    public boolean leafSimilar(TreeNode t1, TreeNode t2) {
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        process(t1, l1);
        process(t2, l2);
        if (l1.size() == l2.size()) {
            for (int i = 0; i < l1.size(); i++) {
                if (!l1.get(i).equals(l2.get(i))) return false;
            }
            return true;
        }
        return false;
    }
    void process(TreeNode root, List<Integer> list) {
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (root.left == null && root.right == null) list.add(root.val);
            root = root.right;
        }
    }
}
复制代码


  • 时间复杂度:nm 分别代表两棵树的节点数量。复杂度为 O(n+m)O(n + m)O(n+m)
  • 空间复杂度:nm 分别代表两棵树的节点数量,当两棵树都只有一层的情况,所有的节点值都会被存储在 listlistlist 中。复杂度为 O(n+m)O(n + m)O(n+m)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.872 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
7月前
|
存储 监控 Java
《从头开始学java,一天一个知识点》之:数组入门:一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间?** - 看了三天教程,连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;,大脑突然空白 - 写出的代码总是莫名报NPE,却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」!我们承诺:每天1分钟,地铁通勤、午休间隙即可完成学习;直击痛点,只讲高频考点和实际开发中的「坑位」;拒绝臃肿,没有冗长概念堆砌,每篇都有可运行的代码标本。明日预告:《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧,帮助你快速掌握Java数组的精髓。
134 23
|
11月前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
4298 113
|
12月前
|
Java 程序员 编译器
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
285 3
|
12月前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
139 1
|
12月前
|
存储 算法 Java
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构,其创建和遍历是编程基础中的基础。通过不同的创建方式,可以根据实际需求灵活地初始化数组。而选择合适的遍历方法,则可以提高代码的可读性和效率。掌握这些基本技能,对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
92 6
JAVA 递归文件夹
private void getAllFileInfo(String path) { File dirFile = new File(path); File[] files = dirFile.
734 0
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案

热门文章

最新文章