dcddc

西米大人的博客

0%

二叉查找树中搜索区间

发表于 更新于 分类于 热度: ℃ 评论: ℃
字数： 319 阅读时长 ≈ 1 分钟
lintcode题目

题目描述

给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
例子：如果有 k1 = 10 和 k2 = 22, 你的程序应该返回 [12, 20, 22]

1
2
3
4
5
    20
   /  \
  8   22
 / \
4   12

思路

因为是二叉查找树，最直接的方式就是左中右遍历二叉树
对每一个节点，如果其val符合条件，则添加到list
改进算法

针对遍历过程中的每一个root节点，如果其val在查找范围之外，则只选择其一个分支进行递归，直到root的val落在查找范围内，再用基本的二叉查找树遍历算法

代码

基本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        ArrayList<Integer> aList = new ArrayList<>();
	        searchBinaryTree(aList, root, k1, k2);
	        return aList;
    }
    
    private void searchBinaryTree(ArrayList<Integer> alist,TreeNode root, int k1, int k2) {
		 if(root == null) return;
		 
		 searchBinaryTree(alist, root.left, k1, k2);
		 
		 int val = root.val;
		 if(val >= k1 && val <= k2) {
			 alist.add(val);
		 }
		 
		 searchBinaryTree(alist, root.right, k1, k2);
			
	 }

改进算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
	        ArrayList<Integer> aList = new ArrayList<>();
	        mySearch(aList, root, k1, k2);
	        return aList;
	    }

	 private void mySearch(ArrayList<Integer> alist,TreeNode root, int k1, int k2) {
		 if(root == null) return;
		 
		 int val = root.val;
		 if(val < k1) {
			 mySearch(alist, root.right, k1, k2); 
		 } else if(val > k2) {
			 mySearch(alist, root.left, k1, k2); 
		 }	else {
			 searchBinaryTree(alist, root, k1, k2);
		 }
	 }
	 
	 private void searchBinaryTree(ArrayList<Integer> alist,TreeNode root, int k1, int k2) {
         if(root == null) return;

         searchBinaryTree(alist, root.left, k1, k2);

         int val = root.val;
         if(val >= k1 && val <= k2) {
             alist.add(val);
         }

         searchBinaryTree(alist, root.right, k1, k2);

     }

考察点

  • 二叉查找树的遍历