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.

Have you met this question in a real interview?  Yes Example

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

20 / \ 8 22 / \ 4 12

这是一道树的遍历题，利用二叉搜索树的性质，如果当前节点的值在这两个值得范围里，那么结果应该在以这个点作为根的子树立。那么先递归调用当前节点的左孩子，然后加入当前节点的值到结果集，然后递归调用当前节点的右孩子（因为要保序，所以先左边，然后自己，然后再后边这个顺序）。如果这个节点的值比low还要小，说明结果应该在有孩子，反之在左孩子，往两个不同的方向递归。然后注意下node== null的情况直接return就好了。

代码：

public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if(root == null) return result; dfs(result, root, k1, k2); return result; } private void dfs(ArrayList<Integer> result, TreeNode node, int low, int high){ if(node == null) return; if(node.val>=low && node.val<=high){ dfs(result, node.left, low, high); result.add(node.val); dfs(result, node.right,low, high); }else if(node.val < low){ dfs(result, node.right, low, high); }else if(node.val > high){ dfs(result, node.left, low, high); } }