首页 > 代码库 > LintCode-Search Range in Binary Search Tree
LintCode-Search Range in Binary Search Tree
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
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
20
/ \
8 22
/ \
4 12
Solution:
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * }10 * }11 */12 public class Solution {13 /**14 * @param root: The root of the binary search tree.15 * @param k1 and k2: range k1 to k2.16 * @return: Return all keys that k1<=key<=k2 in ascending order.17 */18 public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {19 ArrayList<Integer> res = searchRangeRecur(root,k1,k2);20 return res;21 }22 23 public ArrayList<Integer> searchRangeRecur(TreeNode cur, int k1, int k2){24 ArrayList<Integer> res = new ArrayList<Integer>();25 if (cur==null) return res;26 if (k1>k2) return res;27 28 ArrayList<Integer> left = searchRangeRecur(cur.left,k1,Math.min(cur.val-1,k2));29 ArrayList<Integer> right = searchRangeRecur(cur.right,Math.max(cur.val+1,k1),k2);30 31 res.addAll(left);32 if (cur.val>=k1 && cur.val<=k2) res.add(cur.val);33 res.addAll(right);34 35 return res;36 }37 38 }
LintCode-Search Range in Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。