LeetCode：二叉搜索树的属性、修改与构造（12道经典题目）
本文带来与二叉搜索树的属性、修改与构造有关的经典题目，主要实现是C++。
首先明确一下二叉搜索树的概念：
二叉搜索树是一个有序树，满足如下三个条件：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
特别注意的是，二叉搜索树的中序遍历是一个升序数组！！！
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) return root;
if (root->val > val) return searchBST(root->left, val);
if (root->val < val) return searchBST(root->right, val);
return nullptr;
}
};
因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != nullptr) {
if (root->val == val) return root;
else if (root->val < val) root = root->right;
else root = root->left;
}
return nullptr;
}
};
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
中序遍历下，输出的二叉搜索树节点的数值是有序序列。
class Solution {
public:
bool isValidBST(TreeNode* root) {
vec.clear();
traversal(root);
for (int i = 1; i < vec.size(); i++) {
if (vec[i] <= vec[i - 1]) return false;
}
return true;
}
void traversal(TreeNode* cur) {
if (cur == nullptr) return;
traversal(cur->left);
vec.push_back(cur->val);
traversal(cur->right);
}
vector<int> vec;
};
二叉搜索树里不能有相同元素
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
bool left = isValidBST(root->left);
if (root->val > maxValue) maxValue = root->val;
else return false;
bool right = isValidBST(root->right);
return left && right;
}
long long maxValue = LONG_MIN;
};
以上代码是因为后台数据有int最小值测试用例，所以都把maxVal改成了longlong最小值。如果测试数据中有 longlong的最小值，怎么办？建议避免初始化最小值，如下方法取到最左面节点的数值来比较。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
bool left = isValidBST(root->left);
if (pre != nullptr && pre->val >= root->val) return false;
pre = root;
bool right = isValidBST(root->right);
return left && right;
}
TreeNode* pre;
};
迭代法求解：（只用稍微更改中序遍历）
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while (cur != nullptr || !st.empty()) {
if (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top(); st.pop();
if (pre != nullptr && pre->val >= cur->val) return false;
pre = cur;
cur = cur->right;
}
}
return true;
}
};
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
最简单的方法就是把二叉搜索树编程一个列表，这样求最小差值就很简单了。
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
vec.clear();
traversal(root);
int maxDiff = INT_MAX;
for (int i = 1; i < vec.size(); i++) {
maxDiff = min(maxDiff, vec[i] - vec[i - 1]);
}
return maxDiff;
}
void traversal(TreeNode* cur) {
if (cur == nullptr) return;
traversal(cur->left);
vec.push_back(cur->val);
traversal(cur->right);
return;
}
vector<int> vec;
};
记录前一个节点，在遍历过程中直接计算：
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
void traversal(TreeNode* root) {
if (root == nullptr) return;
if (root->left) getMinimumDifference(root->left);
if (pre != nullptr) {
result = min(result, root->val - pre->val);
}
pre = root;
if (root->right) getMinimumDifference(root->right);
}
private:
int result = INT_MAX;
TreeNode* pre;
};
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即出现频率最高的元素）。如果树中有不止一个众数，可以按 任意顺序 返回。假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
如果不是二叉搜索树：
class Solution {
public:
vector<int> findMode(TreeNode* root) {
map.clear();
traversal(root);
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp);
vector<int> result;
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
if (vec[0].second == vec[i].second) result.push_back(vec[i].first);
else break;
}
return result;
}
bool static cmp(pair<int, int>& a, pair<int, int>& b) {
return a.second > b.second; // 按照频率从大到小排序
}
void traversal(TreeNode* cur) {
if (cur == nullptr) return;
traversal(cur->left);
map[cur->val]++;
traversal(cur->right);
return;
}
map<int, int> map;
};
C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序。所以要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。
是二叉搜索树：
既然是搜索树，它中序遍历就是有序的！
从头遍历，比较相邻两个节点的元素，然后就把出现频率最高的元素输出。定义指针pre指向前一个节点，这样就可以比较相邻节点了。
class Solution {
public:
vector<int> findMode(TreeNode* root) {
count = 0;
maxCount = 0;
TreeNode* pre = nullptr;
result.clear();
traversal(root);
return result;
}
void traversal(TreeNode* cur) {
if (cur == nullptr) return;
traversal(cur->left);
if (pre == nullptr) count = 1; // 第一个节点
else if (pre->val == cur->val) count++;
else count = 1; // 与前一个节点数值不同
pre = cur; // 更新上一个节点
if (count == maxCount) result.push_back(cur->val);
else if (count > maxCount) {
maxCount = count;
result.clear();
result.push_back(cur->val);
}
traversal(cur->right);
return;
}
private:
TreeNode* pre;
int maxCount; // 最大频率
int count; // 统计频率
vector<int> result;
};
class Solution {
public:
vector<int> findMode(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* pre = nullptr;
TreeNode* cur = root;
int maxCount = 0;
int count = 0;
vector<int> vec;
while (cur != nullptr || !st.empty()) {
if (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top();
st.pop();
if (pre == nullptr) count = 1;
else if (pre->val == cur->val) count++;
else count = 1;
pre = cur;
if (maxCount == count) {
vec.push_back(cur->val);
}
if (maxCount < count) {
maxCount = count;
vec.clear();
vec.push_back(cur->val);
}
cur = cur->right;
}
}
return vec;
}
};
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
利用回溯自底向上查找！后序遍历就是天然的回溯过程，最先处理的一定是叶子节点。
**如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。**使用后序遍历，回溯的过程，就是从低向上遍历节点，一旦发现如何这个条件的节点，就是最近公共节点了。
如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法：
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == p || root == q || root == nullptr) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) return root;
if (left == nullptr && right != nullptr) return right;
else if (left != nullptr && right == nullptr) return left;
else return nullptr;
}
};
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
其实只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
if (cur == nullptr) return cur;
if (cur->val > p->val && cur->val > q->val) {
TreeNode* left = traversal(cur->left, p, q);
if (left != nullptr) return left;
}
if (cur->val < p->val && cur->val < q->val) {
TreeNode* right = traversal(cur->right, p, q);
if (right != nullptr) return right;
}
return cur;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
if (root->val > p->val && root->val > q->val) {
root = root->left;
}
else if (root->val < p->val && root->val < q->val) {
root = root->right;
}
else return root;
}
return nullptr;
}
};
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
递归函数不用返回值也可以，找到插入的节点位置，直接让其父节点指向插入节点，结束递归。没有返回值，需要记录上一个节点（parent），遇到空节点了，就让parent左孩子或者右孩子指向新插入的节点。然后结束递归。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
parent = new TreeNode(0);
if (root == nullptr) {
root = new TreeNode(val);
}
traversal(root, val);
return root;
}
void traversal(TreeNode* cur, int val) {
if (cur == nullptr) {
TreeNode* node = new TreeNode(val);
if (val > parent->val) parent->right = node;
else parent->left = node;
return;
}
parent = cur;
if (cur->val < val) traversal(cur->right, val);
if (cur->val > val) traversal(cur->left, val);
return;
}
TreeNode* parent;
};
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode* node = new TreeNode(val);
return node;
}
TreeNode* cur = root;
TreeNode* parent = nullptr;
while (cur != nullptr) {
parent = cur;
if (cur->val > val) cur = cur->left;
else cur = cur->right;
}
TreeNode* node = new TreeNode(val);
if (val < parent->val) parent->left = node;
else parent->right = node;
return root;
}
};
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：
有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key) {
if (root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
else if (root->left == nullptr) {
TreeNode* retNode = root->right;
delete root;
return retNode;
}
else if (root->right == nullptr) {
TreeNode* retNode = root->left;
delete root;
return retNode;
}
else {
TreeNode* cur = root->right;
while (cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left;
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
}
if (root->val < key) root->right = deleteNode(root->right, key);
if (root->val > key) root->left = deleteNode(root->left, key);
return root;
}
};
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
// 修剪的操作并不是在终止条件上进行的，遇到空节点返回就可以了。
if (root == nullptr) return nullptr;
// 如果当前节点的元素小于low的数值，那么应该递归右子树
if (root->val < low) {
return trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
}
// 当前节点的元素大于high的，那么应该递归左子树
if (root->val > high) {
return trimBST(root->left, low, high);
}
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
}
};
因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。在剪枝的时候，可以分为三步：
- 将root移动到[L, R] 范围内，注意是左闭右闭区间
- 剪枝左子树
- 剪枝右子树
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
// 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
while (root != nullptr && (root->val < low || root->val > high)) {
if (root->val < low) root = root->right;
else root = root->left;
}
TreeNode* cur = root;
// 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
while (cur != nullptr) {
while (cur->left != nullptr && cur->left->val < low) {
cur->left = cur->left->right;
}
cur = cur->left;
}
cur = root;
// 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
while (cur != nullptr) {
while (cur->right != nullptr && cur->right->val > high) {
cur->right = cur->right->left;
}
cur = cur->right;
}
return root;
}
};
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为默认都是从数组中间位置取值作为节点元素，一般不会随机取。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。有序数组构造二叉搜索树，寻找分割点比较容易，分割点就是数组中间位置的节点。如果数组长度为偶数，中间节点有两个，取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return traversal(nums, 0, nums.size() - 1);
}
// 左闭右闭
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
};
迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return nullptr;
TreeNode* root = new TreeNode(0); // 初始根节点
queue<TreeNode*> nodeQue; // 放遍历的节点
queue<int> leftQue; // 保存左区间下标
queue<int> rightQue; // 保存右区间下标
nodeQue.push(root);
leftQue.push(0);
rightQue.push(nums.size() - 1);
while (!nodeQue.empty()) {
TreeNode* curNode = nodeQue.front(); nodeQue.pop();
int left = leftQue.front(); leftQue.pop();
int right = rightQue.front(); rightQue.pop();
int mid = left + (right - left) / 2;
curNode->val = nums[mid];
if (left <= mid - 1) { // 处理左区间
curNode->left = new TreeNode(0);
nodeQue.push(curNode->left);
leftQue.push(left);
rightQue.push(mid - 1);
}
if (right > mid) { // 处理右区间
curNode->right = new TreeNode(0);
nodeQue.push(curNode->right);
leftQue.push(mid + 1);
rightQue.push(right);
}
}
return root;
}
};
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
PS. 这道题和下面这道题一模一样，读不懂的可以看下面这道题。
给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
class Solution {
public:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* root) {
if (root == nullptr) return;
traversal(root->right); // 右
root->val += pre; // 中
pre = root->val;
traversal(root->left); // 左
return;
}
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr) return nullptr;
stack<TreeNode*> st;
TreeNode* cur = root;
int pre = 0;
while (cur != nullptr || !st.empty()) {
if (cur != nullptr) {
st.push(cur);
cur = cur->right; // 右
}
else {
cur = st.top();
st.pop();
cur->val += pre; // 中
pre = cur->val;
cur = cur->left; // 左
}
}
return root;
}
};
以上题解大多来自【代码随想录】（完整版看这个！！），在此基础上做了一定总结，并附带一些自己的理解。
后续题目，随缘更新，有错误请指出！
END
