# 剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
private:
void DFS(Node *root) {
if(root == NULL) return;

DFS(root->left);
else pre->right = root;

root->left = pre;
pre = root;
DFS(root->right);
}
public:
Node* treeToDoublyList(Node* root) {

if(root == NULL) return NULL;

DFS(root);

}
};

# LeetCode Construct Binary Search Tree from Preorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]



Note:

1. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

class Solution {
public:
TreeNode* Work(vector<int> &preorder, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(preorder[l]);
TreeNode *root = new TreeNode(preorder[l]);
int mid = -1;
for (int i = l; i <= r; ++i) {
if (preorder[i] > root->val) {
mid = i;
break;
}
}
if (mid == -1)root->left = Work(preorder, l + 1, r);
else {
root->left = Work(preorder, l + 1, mid - 1);
root->right = Work(preorder, mid, r);
}
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
return Work(preorder, 0, preorder.size() - 1);
}
};

# LeetCode Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.


Constraints:

• The number of nodes in the tree is between 1 and 10^4.
• The tree nodes will have distinct values between 1 and 10^5.

class Solution {
public:
void preIter(TreeNode* root, vector<int> &nums) {
if (root == NULL)return;
preIter(root->left, nums);
nums.push_back(root->val);
preIter(root->right, nums);
}
TreeNode* constructBST(vector<int> &nums, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(nums[l]);

int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = constructBST(nums, l, mid - 1);
root->right = constructBST(nums, mid + 1, r);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
preIter(root, nums);
int n = nums.size();
return constructBST(nums, 0, n - 1);
}
};

# LeetCode Contains Duplicate III

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true


Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true


Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false

typedef long long ll;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
set<ll> window;
for (int i = 0; i < nums.size(); ++i) {
if (i > k)
window.erase(nums[i – k – 1]); // 删除窗口左边的元素
auto it = window.lower_bound(ll(nums[i]) – t); // x>=nums[i]-t
if (it != window.end() && *it – nums[i] <= t)
return true; // x<=nums[i]+t
window.insert(nums[i]);
}
return false;
}
};

# LeetCode Kth Smallest Element in a BST

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1:

Input: root = [3,1,4,null,2], k = 1
3
/ \
1   4
\
2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3   6
/ \
2   4
/
1
Output: 3


What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Constraints:

• The number of elements of the BST is between 1 to 10^4.
• You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

class Solution {
private:
void inOrder(TreeNode* root, int& k, int& target)
{
if (k < 0)
return;
if (root->left)
inOrder(root->left, k, target);
–k;
if (k == 0)
target = root->val;
if (root->right)
inOrder(root->right, k, target);
}
public:
int kthSmallest(TreeNode* root, int k)
{
int target;
inOrder(root, k, target);
return target;
}
};

rank属性可以在建BST时完成。

# LeetCode Convert BST to Greater Tree

LeetCode Convert BST to Greater Tree Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example:

Input: The root of a Binary Search Tree like this:
5
/   \
2     13
Output: The root of a Greater Tree like this:
18
/   \
20     13

# LeetCode Minimum Absolute Difference in BST

LeetCode Minimum Absolute Difference in BST Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example:

Input:
1
\
3
/
2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

# LeetCode Delete Node in a BST

LeetCode Delete Node in a BST Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.
Note: Time complexity should be O(height of tree). Example:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3   6
/ \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/ \
4   6
/     \
2       7
5
/ \
2   6
\   \
4   7

       root
/    \
left  right
/   \  /   \
x    l r     y

    left            right
/  \            /   \
x               r     y
/
l 

            left
/  \
x    right
/   \
r     y
/
l  

# LeetCode Validate Binary Search Tree

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

    2
/ \
1   3

Input: [2,1,3]
Output: true


Example 2:

    5
/ \
1   4
/ \
3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

    10
/ \
5   15
/  \
13   20
/  \
6   14
class Solution {
public:
bool helper(TreeNode* root, long long minVal, long long maxVal)
{
if (root == NULL)
return true;
if (root->val <= minVal || root->val >= maxVal)
return false;
return helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal);
}
bool isValidBST(TreeNode* root)
{
long long minVal = LLONG_MIN, maxVal = LLONG_MAX;
return helper(root, minVal, maxVal);
}
};

class Solution {
public:
bool isBST(TreeNode* root, int &max_val, int &min_val) {
if (root == NULL) {
max_val = INT_MIN;
min_val = INT_MAX;
return true;
}
// 以root为根的子树的最大和最小值
max_val = root->val;
min_val = root->val;
if (root->left == NULL && root->right == NULL) {
return true;
}
if (root->left) {
int left_max = INT_MIN, left_min = INT_MAX;
bool left_tree = isBST(root->left, left_max, left_min);
if (!left_tree || left_max >= root->val)return false;
min_val = min(min_val, left_min);
}

if (root->right) {
int right_max = INT_MIN, right_min = INT_MAX;
bool right_tree = isBST(root->right, right_max, right_min);
if (!right_tree || right_min <= root->val)return false;
max_val = max(max_val, right_max);
}
return true;
}

bool isValidBST(TreeNode* root) {
int max_val = INT_MIN, min_val = INT_MAX;
return isBST(root, max_val, min_val);
}
};

# LeetCode Find Mode in Binary Search Tree

LeetCode Find Mode in Binary Search Tree Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.
For example: Given BST [1,null,2,2],
   1
\
2
/
2

return [2]. Note: If a tree has more than one mode, you can return them in any order. Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).