1609. 奇偶树 :「BFS」&「DFS」

简介: 1609. 奇偶树 :「BFS」&「DFS」

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

题目描述



这是 LeetCode 上的 1609. 奇偶树 ,难度为 中等


Tag : 「层序遍历」、「BFS」、「DFS」


如果一棵二叉树满足下述几个条件,则可以称为 奇偶树


二叉树根节点所在层下标为 00 ,根的子节点所在层下标为 11 ,根的孙节点所在层下标为 22 ,依此类推。


  • 偶数下标 层上的所有节点的值都是 整数,从左到右按顺序 严格递增
  • 奇数下标 层上的所有节点的值都是 整数,从左到右按顺序 严格递减


给你二叉树的根节点,如果二叉树为 奇偶树 ,则返回 true ,否则返回 false


示例 1:


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


输入:root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出:true
解释:每一层的节点值分别是:
0 层:[1]
1 层:[10,4]
2 层:[3,7,9]
3 层:[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增,而 1 层和 3 层上的节点值都是偶数且严格递减,因此这是一棵奇偶树。
复制代码


示例 2:


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


输入:root = [5,4,2,3,3,7]
输出:false
解释:每一层的节点值分别是:
0 层:[5]
1 层:[4,2]
2 层:[3,3,7]
2 层上的节点值不满足严格递增的条件,所以这不是一棵奇偶树。
复制代码


示例 3:


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


输入:root = [5,9,1,3,5,7]
输出:false
解释:1 层上的节点值应为偶数。
复制代码


示例 4:


输入:root = [1]
输出:true
复制代码


示例 5:


输入:root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出:true
复制代码


提示:


  • 树中节点数在范围 [1, 10^5][1,105]
  • 1 <= Node.val <= 10^61<=Node.val<=106


BFS



考察「层序遍历」,在遍历过程中需要记录层下标,并根据层下标检查进行「节点值的奇偶性」和「是否满足递增/递减」。


额外使用一个布尔变量 flag 记录层序是否为偶数(判断节点值的奇偶性),使用 prev 记录当前层的上一节点的值(判断是否满足递增/递减)即可,prev 起始值可根据数据范围设置为哨兵值。


代码:


class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        boolean flag = true;
        d.addLast(root);
        while (!d.isEmpty()) {
            int size = d.size(), prev = flag ? 0 : 0x3f3f3f3f;
            while (size-- > 0) {
                TreeNode node = d.pollFirst();
                int cur = node.val;
                if (flag && (cur % 2 == 0 || cur <= prev)) return false;
                if (!flag && (cur % 2 != 0 || cur >= prev)) return false;
                prev = cur;
                if (node.left != null) d.addLast(node.left);
                if (node.right != null) d.addLast(node.right);
            }
            flag = !flag;
        }
        return true;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


DFS



同样的思路,自然也能够使用 DFS 进行求解。


由于 DFS 是深度优先,因此我们在 DFS 过程中除了要记录当前层编号(判断节点值的奇偶性),还要记录每层最后上一次遍历到的节点值为多少(判断是否满足递增/递减)。


代码:


class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public boolean isEvenOddTree(TreeNode root) {
        return dfs(root, 0);
    }
    boolean dfs(TreeNode root, int idx) {
        boolean flag = idx % 2 == 0;
        int prev = map.getOrDefault(idx, flag ? 0 : 0x3f3f3f3f), cur = root.val;
        if (flag && (cur % 2 == 0 || cur <= prev)) return false;
        if (!flag && (cur % 2 != 0 || cur >= prev)) return false;
        map.put(idx, root.val);
        if (root.left != null && !dfs(root.left, idx + 1)) return false;
        if (root.right != null && !dfs(root.right, idx + 1)) return false;
        return true;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


最后



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


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


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


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

相关文章
|
SQL JSON Java
【Elasticsearch专栏 10】深入探索:Elasticsearch如何进行数据导入和导出
在Elasticsearch中,数据导入常通过Bulk API、Logstash或Java客户端进行,支持JSON、CSV等格式。导出则可通过SQL查询、Scroll API或第三方工具如elasticdump实现,将数据以JSON、CSV等格式导出。这些方法确保了数据的高效、安全导入与导出。
1399 5
|
存储 缓存 Unix
微信小游戏制作工具中实现计时功能
微信小游戏制作工具中实现计时功能
574 0
|
4月前
|
机器学习/深度学习 算法 物联网
《探秘边缘智能:ESP32搭载TinyML实现语音唤醒的深度解析》
TinyML(微型机器学习)是一种将机器学习能力引入资源受限的边缘设备(如微控制器和物联网设备)的技术。与依赖云端计算的传统方法不同,TinyML通过算法优化、模型压缩和量化技术,在低功耗设备上实现实时智能决策。ESP32作为一款集成Wi-Fi和蓝牙功能的微控制器,凭借其强大的处理能力和低功耗特性,成为TinyML应用的理想平台。 以语音唤醒为例,TinyML结合ESP32可实现设备在待机状态下实时监测特定唤醒词的功能。这一过程需克服环境噪音、多样化人声特征及资源限制等挑战。构建语音唤醒模型涉及数据收集与预处理、轻量级神经网络设计(如CNN)、模型训练与优化、量化以及部署到ESP32上运行。
236 0
|
6月前
|
编解码 Linux iOS开发
Shotcut 25.03 (Linux, macOS, Windows) - 免费开源视频编辑器
Shotcut 25.03 (Linux, macOS, Windows) - 免费开源视频编辑器
312 11
|
11月前
|
JSON BI API
商城上货API接口的实战案例
在商城上货过程中,API接口扮演着至关重要的角色。以下是对商城上货API接口的实战分析,涵盖其主要功能、类型、安全性以及实战案例等方面。
|
人工智能 自然语言处理 算法
阿里云PAI大模型评测最佳实践
在大模型时代,模型评测是衡量性能、精选和优化模型的关键环节,对加快AI创新和实践至关重要。PAI大模型评测平台支持多样化的评测场景,如不同基础模型、微调版本和量化版本的对比分析。本文为您介绍针对于不同用户群体及对应数据集类型,如何实现更全面准确且具有针对性的模型评测,从而在AI领域可以更好地取得成就。
|
存储 算法 程序员
【C/C++ 随机数】深入探索C++随机数生成,random 模块的应用
【C/C++ 随机数】深入探索C++随机数生成,random 模块的应用
749 0
|
存储 缓存 运维
解密一致性哈希算法:实现高可用和负载均衡的秘诀
解密一致性哈希算法:实现高可用和负载均衡的秘诀
1567 0
|
C++ 容器
项目案例一:基于C++的图书馆管理系统
项目案例一:基于C++的图书馆管理系统
487 0
|
人工智能 自然语言处理 小程序