Search Range in Binary Search Tree
今天是一道有关二叉树的题目，来自LintCode，难度为Medium。
题目如下
Given two values
k1andk2(wherek1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in rangek1tok2. i.e. print allxsuch thatk1<=x<=k2andxis a key of given BST. Return all the keys in ascending order.
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，老规矩，看到二叉树，想到二叉树的三种遍历方式。
然后，这是是按升序排序，很明显是中序遍历。
其次，知道了采用中序遍历，下面就要考虑两个问题：
每个节点如何处理，从题目中很容易看出，当该节点的值在k1和k2之间时加入链表，否则跳过。
递归的终止条件：比较明显，即当节点的值比
k1小或者比k2大时终止。即此时，不在遍历该节点的左右子树。
最后，我们来看代码。
代码如下
Java版
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
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.
*/
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
midOrder(list, root, k1, k2);
return list;
}
private void midOrder(List<Integer> ret, TreeNode root, int k1, int k2) {
if(null == root)
return;
boolean biggerK1 = root.val >= k1;
boolean smallerK2 = root.val <= k2;
if(biggerK1)
midOrder(ret, root.left, k1, k2);
if(biggerK1 && smallerK2)
ret.add(root.val);
if(smallerK2)
midOrder(ret, root.right, k1, k2);
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
