Lintcode: Search Range in Binary Search Tree
in Tree search Binary range lintcode
2023-09-11 14:14:07 时间
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
我的做法是inorder traversal的变形,判断是否向左边递归的时候加上判断是否:root.val > k1, 如果否,则不需要继续向左递归;右子树的处理方法类似
第一次做法,把result数组作为return type,不好,消耗额外空间
1 public class Solution { 2 /** 3 * @param root: The root of the binary search tree. 4 * @param k1 and k2: range k1 to k2. 5 * @return: Return all keys that k1<=key<=k2 in ascending order. 6 */ 7 public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { 8 ArrayList<Integer> res = searchRangeRecur(root,k1,k2); 9 return res; 10 } 11 12 public ArrayList<Integer> searchRangeRecur(TreeNode cur, int k1, int k2){ 13 ArrayList<Integer> res = new ArrayList<Integer>(); 14 if (cur==null) return res; 15 if (k1>k2) return res; 16 17 ArrayList<Integer> left = searchRangeRecur(cur.left,k1,Math.min(cur.val-1,k2)); 18 ArrayList<Integer> right = searchRangeRecur(cur.right,Math.max(cur.val+1,k1),k2); 19 20 res.addAll(left); 21 if (cur.val>=k1 && cur.val<=k2) res.add(cur.val); 22 res.addAll(right); 23 24 return res; 25 } 26 27 }
第二遍做法:
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 // write your code here 20 ArrayList<Integer> res = new ArrayList<Integer>(); 21 if (root == null || (k1 > k2)) return res; 22 helper(root, k1, k2, res); 23 return res; 24 } 25 26 public void helper(TreeNode root, int k1, int k2, ArrayList<Integer> res) { 27 if (root == null) return; 28 helper(root.left, k1, k2, res); 29 if (k1 <= root.val && root.val <= k2) res.add(root.val); 30 helper(root.right, k1, k2, res); 31 } 32 }
相关文章
- ALTER TABLE causes auto_increment resequencing, resulting in duplicate entry ’1′ for key
- [Javascript] Deep Search nested tag element in DOM tree
- MySQL 数据库 [Err] 1093 - You can't specify target table 'd_alarm' for update in FROM clause
- [Algorithms] Tree Data Structure in JavaScript
- Execution error: 'the function name is not a recognized built-in function name'
- SAP Enterprise search test report ESH_TEST_SEARCH debug in Q2D
- How is syntax error in Vue detected - Vue的语法错误检查机制介绍
- Atitit. Exception in thread "main" java.lang.Error: Unresolved compilation problem:
- how CRM One Order search by contact name work in the past
- 【目标检测】35、PISA: Prime Sample Attention in Object Detection
- AI:2020年6月24日北京智源大会演讲分享之知识智能专题论坛——12:30-13:10Jure《Recent Advancements in Graph Neural Networks》
- 已解决FutureWarning: The default value of regex will change from True to False in a future version. In
- is not in the sudoers file.This incident will be reported
- leetcode 671. Second Minimum Node In a Binary Tree
- PAT 1151 LCA in a Binary Tree C++版
- 【异常】FlinkException: The module flink-runtime-web could not be found in the class path