算法面试真题详解:二叉查找树中搜索区间-阿里云开发者社区

开发者社区> 算法编程> 正文

算法面试真题详解:二叉查找树中搜索区间

简介: 算法面试真题详解:二叉查找树中搜索区间

给定一个二叉查找树和范围[k1, k2]。按照升序返回给定范围内的节点值。

在线评测地址:领扣题库官网

样例 1:

输入:{5},6,10
输出:[]
        5
它将被序列化为 {5}
没有数字介于6和10之间

样例 2:

输入:{20,8,22,4,12},10,22
输出:[12,20,22]
解释:
        20
       /  \
      8   22
     / \
    4   12
它将被序列化为 {20,8,22,4,12}
[12,20,22]介于10和22之间

解题思路

这题考查的是二叉查找树的性质,以及二叉树的中序遍历。
二叉查找树满足左子树所有节点的值都小于当前节点的值,右子树所有节点的值都大于当前节点的值。二叉查找树的中序遍历是一个排好序的序列。
这题我们在中序遍历的过程中将在数值范围内的值按序加入到数组中,就能得到最终的结果。

代码思路

二叉树中序遍历:

  1. 如果当前节点为空,直接返回。
  2. 先遍历左节点。
  3. 判断当前节点的值是否在范围内,如果是,加入结果数组中。
  4. 再遍历右节点。
    这题有一个可以剪枝的技巧,如果已经可以确定左子树或右子树不在数值范围内,可以不遍历相应的子树。

复杂度分析

设二叉树的节点数为N。
时间复杂度

  • 遍历一遍二叉树的时间复杂度为O(N)。
    空间复杂度
  • 递归的空间开销取决于树的最大深度,空间复杂度为O(N)。
public class Solution {
    /**
     * @param root: param root: The root of the binary search tree
     * @param k1: An integer
     * @param k2: An integer
     * @return: return: Return all keys that k1<=key<=k2 in ascending order
     */
    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        List<Integer> result = new ArrayList<>();
        travel(root, k1, k2, result);
        return result;
    }
    private void travel(TreeNode root, int k1, int k2, List<Integer> result) {
        if (root == null) {
            return;
        }
        // 剪枝,如果当前节点小于等于k1,不必访问左子树
        if (root.val > k1) {
            travel(root.left, k1, k2, result);
        }
        if (k1 <= root.val && root.val <= k2) {
            result.add(root.val);
        }
        // 剪枝,如果当前节点大于等于k2,不必访问右子树
        if (root.val < k2) {
            travel(root.right, k1, k2, result);
        }
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接