算法 中等 | 11. 二叉查找树中搜索区间

• 题目描述
• • 样例1
  • 样例2
• 解题思路
• java题解
• C++题解
• python题解

题目描述

给定一个二叉查找树和范围[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）左、右子树也分别为二叉排序树；

题解：从给定的BST的根节点开始查找，如果当前节点大于k1，就向左子树搜索，如果当前节点小于k2，就继续向右子树搜索。如果位于[k1,k2]，存入结果。

java题解

public class Solution {
    private ArrayList<Integer> results;
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in increasing order.
     */
    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        results = new ArrayList<Integer>();
        helper(root, k1, k2);
        return results;
    }
    
    private void helper(TreeNode root, int k1, int k2) {
        if (root == null) {
            return;
        }
        if (root.val > k1) {
            helper(root.left, k1, k2);
        }
        if (root.val >= k1 && root.val <= k2) {
            results.add(root.val);
        }
        if (root.val < k2) {
            helper(root.right, k1, k2);
        }
    }
}
           

C++题解

class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in increasing order.
     */
    vector<int> ans;
    void  dfs(TreeNode* node, int k1, int k2) {
       
        if (node->left && node->val>=k1)
            dfs(node->left, k1, k2);
         if (node->val >= k1 && node->val <= k2)
            ans.push_back(node->val);
        if (node->right && node->val<=k2)
            dfs(node->right, k1, k2);
    }
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        // write your code here
        if (root==NULL)
            return ans;
        dfs(root, k1, k2);
        return ans;
    }
};
           

python题解

class Solution:
    """
    @param root: The root of the binary search tree.
    @param k1 and k2: range k1 to k2.
    @return: Return all keys that k1<=key<=k2 in increasing order.
    """     
    def searchRange(self, root, k1, k2):
        # write your code here
        ans = []
        if root is None:
            return ans
        queue = [root]
        index = 0
        while index < len(queue):
            if queue[index] is not None:
                if queue[index].val >= k1 and \
                    queue[index].val <= k2:
                    ans.append(queue[index].val)

                queue.append(queue[index].left)
                queue.append(queue[index].right)

            index += 1
        return sorted(ans)