Search range in a BST

題目：

Given a binary search tree and a range[k1, k2], return all elements in the given range.

。題目假設：

題目給定 BST，BST特點就是左小於根，根小於右

節點的結構已有， k1 不小於 k2

。重要問題

在怎樣的條件下進行下一次遞迴，在遞迴時又是往左還是往右？

。直覺

用遞迴去執行掃描

。解決方法可行性

寫一個走訪函式，遇到條件對的就把 val 丟進結果裡

。解決方案

初始結果的 list

從 root 開始遍歷：

• 遇到 null 就回傳
• 當前的值如果大於 k1 -> 表示還沒找到第一個比 k1 小的數字，那麼要繼續往左邊找
• 當前的值如果介於 k1<= x <= k2 區間，則丟進結果
• 當前的值如果小於 k2 -> 表示還沒找到第一個比 k2 大的數字，繼續往右找

。資料結構

TreeNode

an ArrayList to contain the result

。複雜度

在 BST 裡面搜尋是 O( log n)，本題相當於找出 x < k1 && x > k2 的數，因此是 2*O( log n) => O(log n)

。遇到的困難點、想錯的地方

此題無

public class Solution {

    private List<Integer> result;

    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        result = new ArrayList<>();
        if (root == null || k1 > k2) {
            return result;
        }
        helper(root, k1, k2);
        return result;
    }

    private void helper(TreeNode node, int k1, int k2) {
        if (node == null) {
            return;
        }

        if (node.val > k1) {
            helper(node.left, k1, k2);
        }

        if (node.val >= k1 && node.val <= k2) {
            result.add(node.val);
        }

        if (node.val < k2) {
            helper(node.right, k1, k2);
        }
    }      
}