Search Range in BST

godruoyi 發布于2019-08-14 17:07 / 1499人閱讀

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example
If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

BST + Ascending order ---> Inorder
left bound and right bound are given : k1(left) , k2(right)

Invalid area: x < k1 || x > k2
root >= left bound ----> search until reach the left bound
root <= right bound ----> search until reach the right bound

public 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 ascending order.
     */
      private ArrayList results;
    public ArrayList searchRange(TreeNode root, int k1, int k2) {
        results = new ArrayList();
        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);
        }
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66438.html

11.leetcode Range Sum of BST

1. Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive). The binary search tree is guaranteed to have unique values. #### 1. 例子 Inp...

shiweifu 2019-08-23 16:57 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode] 501. Find Mode in Binary Search Tree

Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...

NikoManiac 2019-08-16 13:51 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節點，或者只有一個子樹。思想來自于的代碼實現。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0
[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

摘要：遞歸法復雜度時間空間思路根據二叉樹的性質，我們知道當遍歷到某個根節點時，最近的那個節點要么是在子樹里面，要么就是根節點本身。因為我們知道離目標數最接近的數肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

AlphaWallet 2019-08-14 12:37 評論0 收藏0