算法面試真題詳解：二叉查找樹中搜尋區間

給定一個二叉查找樹和範圍[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