坦率地讲，我一直觉得树这个结构特别复杂，主要是我搞不太清楚递归的过程，所以老是忘（就在刚才，我又忘了怎么把一个有序数组变成BST），主要还是不理解吧……所以就总结一下，方便下次查询。
二叉搜索树BST是一个很常见的结构，并且有一些特别好的性质：
- 节点 N 左子树上的所有节点的值都小于等于节点 N 的值
- 节点 N 右子树上的所有节点的值都大于等于节点 N 的值
- 左子树和右子树也都是 BST
因为有这样的特点，所以BST有一个很重要的特点：中序遍历的结果事实上是一个有序的数组。可以利用这个性质解决一些问题。
此外，为方便说明，下文中的TreeNode结构体定义如下：
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
首先是把有序数组转换成BST，这个可以利用二分法来实现：
TreeNode *getBST(vector<int> &nums, int b, int e)
{
if (b == e)
{
return new TreeNode(nums[b]);
}
if (b > e)
{
return nullptr;
}
int mid = (b + e + 1) / 2;
TreeNode *root = new TreeNode(nums[mid]);
root->left = getBST(nums, b, mid - 1);
root->right = getBST(nums, mid + 1, e);
return root;
}
如果数据量较大，中间求mid的过程可以改成类似于b + ( e - b ) / 2，通过减法来避免加法的上溢。
然后是一类比较特殊的用法：求二叉搜索树的众数和最小绝对差。看起来没啥关系，其实是一类的，都依赖于当前值的上下文，因为二叉搜索树的中序遍历是有序的。假如在数组的语境下，比如说求一个有序数组的众数，第一反应肯定是弄一个计数器，每次遇到不一样的数就清空，然后找出最大的数，大概像这样（如果众数不止一个，都返回）：
vector<int> findModeInArray(vector<int> &arr)
{
vector<int> mode;
int max_count = 0;
int cur_count = 1;
int length = arr.size();
for (int i = 1; i < length; ++i)
{
cur_count = arr[i] == arr[i - 1] ? cur_count + 1 : 1;
if (cur_count == max_count)
{
mode.push_back(arr[i]);
}
else if (cur_count > max_count)
{
mode.clear();
mode.push_back(arr[i]);
max_count = cur_count;
}
}
return mode;
}
如果放到BST的语境下，也是一样的，就是多了一个“翻译”的过程。而且，由于需要递归，需要通过函数的参数来保存当时的上下文。如果使用全局变量，可能会出现全局变量被意外修改的情况。解法来自junstat@LeetCode：
void inOrder(TreeNode* root, TreeNode*& pre, int& curTimes,
int& maxTimes, vector<int>& res){
if (!root) return;
inOrder(root->left, pre, curTimes, maxTimes, res);
if (pre)
curTimes = (root->val == pre->val) ? curTimes + 1 : 1;
if (curTimes == maxTimes)
res.push_back(root->val);
else if (curTimes > maxTimes){
res.clear();
res.push_back(root->val);
maxTimes = curTimes;
}
pre = root;
inOrder(root->right, pre, curTimes, maxTimes, res);
}
vector<int> findMode(TreeNode* root) {
vector<int> res;
if (!root) return res;
TreeNode* pre = NULL;
int curTimes = 1, maxTimes = 0;
inOrder(root, pre, curTimes, maxTimes, res);
return res;
}
可以看到，几乎是完全一致的，唯一的区别在于，数组语境下使用的是for循环来进行遍历，而在BST语境下使用的是递归的中序遍历，然后把每次遍历用到的数据放在了参数里（有点闭包的意思）。
然后是BST的最小绝对差。因为是有序的，最小的绝对差必然在相邻的两个元素之间产生。放在数组语境下，就是每次用后一个减前一个，然后找到差的最小值，没什么可说的；放在BST语境下，也差不多是这样：
void inOrderTraverse(TreeNode *root, TreeNode *&pre, int &min_diff)
{
if (root)
{
inOrderTraverse(root->left, pre, min_diff);
if (pre)
{
min_diff = min(root->val - pre->val, min_diff);
}
pre = root;
inOrderTraverse(root->right, pre, min_diff);
}
}
int getMinimumDifference(TreeNode *root)
{
TreeNode *pre = nullptr;
int min_diff = INT_MAX; // #include <climits>
inOrderTraverse(root, pre, min_diff);
return min_diff;
}
后来又看到一个把BST变成累加树的题目：
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
这个稍微有点特殊，我一开始想的是中序遍历，然后用HashMap保存每个Node对应的累加值，然后再遍历一遍修改原来的树的值（我好像特别喜欢HashMap？）：
unordered_map<int, int> sum_map;
void traverse(TreeNode *root)
{
if (root)
{
traverse(root->left);
for (auto &p : sum_map)
{
p.second += root->val;
}
sum_map[root->val] = root->val;
traverse(root->right);
}
}
void convert(TreeNode *root)
{
if (root)
{
convert(root->left);
root->val = sum_map[root->val];
convert(root->right);
}
}
TreeNode *convertBST(TreeNode *root)
{
traverse(root);
convert(root);
return root;
}
结果跑出来220ms，人都傻了。然后看了题解，发现中序遍历还能倒着用的，当时的心情真是难以言喻：
int sum = 0;
TreeNode *convertBST(TreeNode *root)
{
if (root)
{
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
但是联想一下，如果是在数组语境下，大概也是这么个做法。所以，概括下来，BST的题目大概也就是这么个做法，说起来也很简单：
- 考虑在数组语境下的做法
- 递归进行中序遍历
最后补充一点，CSDN的md编辑器居然不能识别c++，只能识别cpp？