855学习记录数据结构树(6)二叉搜索树的应用——炎泽汐$de$ Blog

二叉搜索树的最小绝对差

---

      中序遍历逐行算差：

TreeNode* pre = nullptr;
int result = INT_MAX;
void traversal(TreeNode* cur) {
    if (!cur){
    	return;
	}
    traversal(cur -> left);
    if (pre){
		result = min(result, cur -> val - pre -> val);
    }
    pre = cur;
    traversal(cur -> right);
}
int getMinimumDifference(TreeNode* root) {
    traversal(root);
    return result;
}

二叉搜索树中的众数

---

      利用中序遍历统计，也可以用 unordered_map 容器来统计：

int maxCount = 0;
int count = 0;
TreeNode* pre = nullptr;
vector<int> result;
void searchBST(TreeNode* cur) {
    if (!cur){
    	return ;
	}

    searchBST(cur -> left);
    if (!pre) {
        count = 1;
    }else if (pre -> val == cur -> val) {
        count++;
    } else {
        count = 1;
    }
    pre = cur;

    if (count == maxCount) {
        result.push_back(cur -> val);
    }

    if (count > maxCount) { 
        maxCount = count;
        result.clear();
        result.push_back(cur -> val);
    }

    searchBST(cur -> right);
    return ;
}

vector<int> findMode(TreeNode* root) {
    count = 0;
    maxCount = 0;
    pre = nullptr;
    result.clear();

    searchBST(root);
    return result;
}

二叉搜索树的最近公共祖先

---

      根据二叉搜索树的特性，最近公共祖先的值一定介于两节点的值之间：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if(root -> val > max(p -> val, q -> val)){
		return lowestCommonAncestor(root -> left, p, q);
	}else if(root -> val < min(p -> val, q -> val)){
		return lowestCommonAncestor(root -> right, p, q);
	}else{
		return root;
	}
}

将有序数组转换为二叉搜索树

---

      在没有平衡因子的条件下将有序数组转化为平衡二叉树：

TreeNode* traversal(vector<int>& nums, int left, int right) {
    if (left > right){
    	return nullptr;
    }
    int mid = left + ((right - left) >> 1);
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = traversal(nums, left, mid - 1);
    root->right = traversal(nums, mid + 1, right);
    return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = traversal(nums, 0, nums.size() - 1);
    return root;
}

把二叉搜索树转换为累加树

---

      反中序遍历即可：

int pre = 0;
void traversal(TreeNode* cur) {
    if(!cur){
    	return;
	}
    traversal(cur -> right);
    cur -> val += pre;
    pre = cur -> val;
    traversal(cur -> left);
}
TreeNode* convertBST(TreeNode* root) {
    pre = 0;
    traversal(root);
    return root;
}