Js源码
二分查找和二叉查找树
33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
思考路程
1 时间复杂度是logn肯定是二分搜索，只不过就是如何二分搜索？
可以先遍历一遍，找到分界点，这里的分界点就是在最小的数字前一个
这里本来想直接找分界点，发现不是很好找，很多测试用例过不去，后来一想，为什么不换一下，改成找最小的数字呢。
449. Serialize and Deserialize BST
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
思考路程
1 就是遍历和重构就可以了，很简单
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Constraints:
0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
思考路程
1 这个很简单，先逆序，然后构建二叉查找树，然后记录下左子树的节点数量
关键是构建良好的数据结构
class TreeNode {
constructor(val, count) {
// 代表二叉排序树中在val的左子树的个数
this.count = count || 0;
this.left = null;
this.right = null;
this.val = val;
}
}
