[LintCode] Search Range in Binary Search Tree

draveness 发布于2019-08-14 15:12 / 1989人阅读

摘要：重点是根据的性质，先左后根最后右。另一重点是，函数和函数都要用的的参数，记得在函数外层定义。

Problem

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].

Note

重点是：根据BST的性质，先左后根最后右。
另一重点是，helper函数和main函数都要用的的参数，记得在main函数外层定义。

Solution

public class Solution {
    private ArrayList result;
    public ArrayList searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        result = new ArrayList();
        Searchfunc(root, k1, k2);
        return result;
    }
    public void Searchfunc(TreeNode root, int k1, int k2) {
        if (root == null) {
            return;
        }
        if (root.val > k1) {
            Searchfunc(root.left, k1, k2);
            }
        if (root.val >= k1 && root.val <= k2) {
            result.add(root.val);
        }
        if (root.val < k2) {
            Searchfunc(root.right, k1, k2);
        }
    }
}

idc机房托管超融合服务器 binary-search-tree binary-search binary-tree search

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65455.html

[LintCode] Remove Node in Binary Search Tree [理解BS

Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

陈江龙 2019-08-14 15:33 评论0 收藏0
[LintCode] Insert Node in a Binary Search Tree

摘要：建立两个树结点，先用找到在的位置，让作为的根节点找到的位置后，指向。此时，用代替与连接就可以了。 Problem Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tr...

Taste 2019-08-14 15:33 评论0 收藏0
[LintCode] Binary Search Tree Iterator

摘要：建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个的函数就要考虑右边的结点。如此，实现函数。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

silencezwm 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Search for a Range [左右边界法/一次循环

摘要：首先，建立二元结果数组，起点，终点。二分法求左边界当中点小于，移向中点，否则移向中点先判断起点，再判断终点是否等于，如果是，赋值给。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...

zhangrxiang 2019-08-14 15:41 评论0 收藏0
Search Range in BST

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 k2root >= left bound ----> search unti...

godruoyi 2019-08-14 17:07 评论0 收藏0