树遍历专题:利用二叉树的中序遍历有序特性|Java 刷题打卡

简介: 树遍历专题:利用二叉树的中序遍历有序特性|Java 刷题打卡

题目描述



这是 LeetCode 上的 938. 二叉搜索树的范围和 ,难度为 简单


Tag : 「树的搜索」、「DFS」、「BFS」


给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。


示例 1:

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


输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32
复制代码



示例 2:

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


输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23
复制代码


提示:


  • 树中节点数目在范围 [1, 2 * 10410^4104] 内
  • 1 <= Node.val <= 10510^5105
  • 1 <= low <= high <= 10510^5105
  • 所有 Node.val 互不相同


基本思路



这又是众多「二叉搜索树遍历」题目中的一道。


二叉搜索树的中序遍历是有序的。


只要对其进行「中序遍历」即可得到有序列表,在遍历过程中判断节点值是否符合要求,对于符合要求的节点值进行累加即可。


二叉搜索树的「中序遍历」有「迭代」和「递归」两种形式。由于给定了值范围 [low,high][low, high][low,high],因此可以在遍历过程中做一些剪枝操作,但并不影响时空复杂度。


递归



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


代码:


class Solution {
    int low, high;
    int ans;
    public int rangeSumBST(TreeNode root, int _low, int _high) {
        low = _low; high = _high;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (low <= root.val && root.val <= high) ans += root.val;
        dfs(root.right);
    }
}
复制代码


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


迭代



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


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


代码:


class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int ans = 0;
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (low <= root.val && root.val <= high) {
                ans += root.val;
            }
            root = root.right;
        }
        return ans;
    }
}
复制代码


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


最后



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


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


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


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

相关文章
|
10天前
|
Java API 数据处理
Java新特性:使用Stream API重构你的数据处理
Java新特性:使用Stream API重构你的数据处理
Java API 开发者
43 0
|
3月前
|
并行计算 Java API
Java List 集合结合 Java 17 新特性与现代开发实践的深度解析及实战指南 Java List 集合
本文深入解析Java 17中List集合的现代用法,结合函数式编程、Stream API、密封类、模式匹配等新特性,通过实操案例讲解数据处理、并行计算、响应式编程等场景下的高级应用,帮助开发者提升集合操作效率与代码质量。
146 1
|
3月前
|
安全 Java 微服务
Java 最新技术和框架实操:涵盖 JDK 21 新特性与 Spring Security 6.x 安全框架搭建
本文系统整理了Java最新技术与主流框架实操内容,涵盖Java 17+新特性(如模式匹配、文本块、记录类)、Spring Boot 3微服务开发、响应式编程(WebFlux)、容器化部署(Docker+K8s)、测试与CI/CD实践,附完整代码示例和学习资源推荐,助你构建现代Java全栈开发能力。
400 0
|
3月前
|
缓存 安全 Java
Java 并发新特性实战教程之核心特性详解与项目实战
本教程深入解析Java 8至Java 19并发编程新特性,涵盖CompletableFuture异步编程、StampedLock读写锁、Flow API响应式流、VarHandle内存访问及结构化并发等核心技术。结合电商订单处理、缓存系统、实时数据流、高性能计数器与用户资料聚合等实战案例,帮助开发者高效构建高并发、低延迟、易维护的Java应用。适合中高级Java开发者提升并发编程能力。
75 0
|
3月前
|
安全 Java API
Java 17 及以上版本核心特性在现代开发实践中的深度应用与高效实践方法 Java 开发实践
本项目以“学生成绩管理系统”为例,深入实践Java 17+核心特性与现代开发技术。采用Spring Boot 3.1、WebFlux、R2DBC等构建响应式应用,结合Record类、模式匹配、Stream优化等新特性提升代码质量。涵盖容器化部署(Docker)、自动化测试、性能优化及安全加固,全面展示Java最新技术在实际项目中的应用,助力开发者掌握现代化Java开发方法。
133 1
|
3月前
|
IDE Java API
Java 17 新特性与微服务开发的实操指南
本内容涵盖Java 11至Java 17最新特性实战,包括var关键字、字符串增强、模块化系统、Stream API、异步编程、密封类等,并提供图书管理系统实战项目,帮助开发者掌握现代Java开发技巧与工具。
177 1
|
3月前
|
Java 数据库连接 API
Java 8 + 特性及 Spring Boot 与 Hibernate 等最新技术的实操内容详解
本内容涵盖Java 8+核心语法、Spring Boot与Hibernate实操,按考试考点分类整理,含技术详解与代码示例,助力掌握最新Java技术与应用。
112 2

热门文章

最新文章