【LeetCode Cookbook（C++ 描述）】一刷二叉搜索树

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉搜索树算法题。

LeetCode #700：Search in a Binary Search Tree 二叉搜索树中的搜索

给定二叉搜索树的根节点 root 和整数值 val 。
在二叉搜索树中找到节点值 = val 的节点，返回以该节点为根的子树，如果节点不存在，返回 null 。

递归法

根据二叉搜索树的性质，在二叉搜索树中查找一个节点，分为以下 3 步:

• 将查找的节点根节点比较，如果相等，则直接返回。
• 如果查找的节点 < 根节点，则在左子树中递归查找。
• 如果查找的节点 > 根节点，则在右子树中递归查找。

类似于二分查找，根据 val 和 root->val 的大小比较，每次就能排除一半的情况。

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == nullptr) return nullptr;//去左子树搜索if (root->val > val) return searchBST(root->left, val);//去右子树搜索if (root->val < val) return searchBST(root->right, val);//当前节点就是目标值return root;}
};

该算法的时间复杂度为 $O(n)$，空间复杂度也为 $O(n)$。

迭代法

同样也是借助二叉搜索树的性质，其实也是 3 步:

• 当 val == root->val ，直接返回 root 。
• 当 val < root->val ，root 就走到 root->left ，继续找。
• 当 val > root->val ，root 就走到 root->right ，继续找。

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->left;else root = root->right;}return nullptr;}
};

LeetCode #98：Validate Binary Search Tree 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

递归法

基本方式依然是比较根节点的左右子节点，但是需要注意，对于每一个节点 root ，root 的整个左子树都要小于 root->val ，整个右子树都要大于 root->val ，因而不能只是判断节点是否是合法 BST 节点（比较自身与左右孩子），而需要使用辅助函数 _isValidBST() ，增加函数的参数列表，记录树的最大值节点 max 与最小值节点 min ，将 max->val > root->val > min->val 这一约束传递给子树的所有节点。

class Solution {
public:bool isValidBST(TreeNode* root) {return _isValidBST(root, nullptr, nullptr);}private:bool _isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {// base caseif (root == nullptr) return true;//若 root->val 不符合 max 和 min 的限制，说明不是合法 BSTif (min != nullptr && root->val <= min->val) return false;if (max != nullptr && root->val >= max->val) return false;//规定左子树的最大值是 root->val，右子树的最小值是 root->valreturn _isValidBST(root->left, min, root) && _isValidBST(root->right, root, max);}
};

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

迭代法

二叉搜索树拥有一个重要性质，即对二叉搜索树进行中序遍历时，得到的结果是一个有序的序列。对于中序遍历而言，访问节点的顺序和处理节点的顺序是不一致的，并且，处理节点是在遍历完左子树之后。我们进行中序遍历的基本思路是：从根节点开始，一层层地遍历，找到左子树最左的那个节点，从它开始处理节点。

利用栈（stack），在遍历过程中，我们需要同时判断「序列是否有序」，在从栈中弹出节点 curr 的时候，和上一次弹出的节点值 pre 作比较——如果 curr 较大，那就继续遍历，否则就可以证明不是二叉搜索树。

class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> stk;TreeNode* pre = nullptr;while (!stk.empty() || root != nullptr) {//一直向左子树走，每一次将当前节点保存到栈中if (root != nullptr) {stk.push(root);root = root->left;}//当前节点为空，证明走到了最左边，从栈中弹出节点//开始对右子树重复上述过程else {TreeNode* cur = stk.top();stk.pop();//判断序列是否有序if (pre != nullptr && cur->val <= pre->val) return false;pre = cur;root = cur->right;}}return true;}
};

LeetCode #530：Minimum Absolute Difference in BST 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。
差值是一个正数，其数值等于两值之差的绝对值。

我们可以通过中序遍历转换为「在一个有序序列中找最小绝对差」的问题。

递归法

class Solution {
public:int getMinimumDifference(TreeNode* root) {traverse(root);return res;}private:TreeNode* prev = nullptr;int res = INT_MAX;//遍历函数void traverse(TreeNode* root) {if (root == nullptr) return;traverse(root->left);//中序遍历位置if (prev != nullptr) res = min(res, root->val - prev->val);prev = root;traverse(root->right);}
};

该算法时间复杂度为 $O(n)$，空间复杂度也为 $O(n)$。

或者，我们可以合并为一个函数，仍然利用全局变量记录：

class Solution {
public:int getMinimumDifference(TreeNode* root) {if (root == nullptr) return 0;getMinimumDifference(root->left);//中序遍历位置if (prev != nullptr) res = min(res, root->val - prev->val);prev = root;getMinimumDifference(root->right);return res;}private:TreeNode* prev = nullptr;int res = INT_MAX;
};

迭代法

同理，也是利用栈来模拟中序遍历的过程：

class Solution {
public:int getMinimumDifference(TreeNode* root) {stack<TreeNode*> stk;int minRes = INT_MAX;//记录前一个节点TreeNode* pre = nullptr;while (!stk.empty() || root != nullptr) {//一直向左子树走，每一次将当前节点保存到栈中if (root != nullptr) {stk.push(root);root = root->left;}//当前节点为空，证明走到了最左边，从栈中弹出节点//开始对右子树重复上述过程else {TreeNode* cur = stk.top();stk.pop();//求最小绝对差if (pre != nullptr) minRes = min(cur->val - pre->val, minRes);pre = cur;root = cur->right;}}return minRes;}
};

LeetCode #501：Find Mode in Binary Search Tree 二叉搜索树中的众数

给你一个含重复值的二叉搜索树的根节点 root ，找出并返回其中的所有众数，即出现频率最高的元素。
如果树中有不止一个众数，可以按任意顺序返回。

我们依然利用中序遍历，在有序序列中寻找众数。利用有序序列所有重复的数字一定连续（即集中在某个数据段内） 这一特性，一遍扫描，判断相邻的元素值是否相等即可。

递归法

特别地，在有序序列中求众数的过程，由于可能存在多个众数，我们用 cnt 来记录当前元素重复的次数，用 maxCnt 记录已经遍历过的元素当中出现最多的元素的出现次数，用 res 记录众数。具体思路如下:

• 比较当前的元素值 lst[i] 与前一个元素值 pre :
• • 如果 lst[i] == pre ，cnt += 1 。
• • 如果 lst[i] > pre ，cnt = 1 。
• 比较当前元素重复的次数 cnt 与 maxCnt :
• • 如果 cnt == maxCnt ，说明当前的元素值 lst[i] 出现的次数等于当前众数出现的次数，将 lst[i] 加入 res 。
• • 如果 cnt > maxCnt ，说明当前的元素值 lst[i] 出现的次数大于当前众数出现的次数，所以将 maxCnt 更新为 cnt ，清空 res ，之后将 lst[i] 加入 res 。

class Solution {
private:void traverse(TreeNode* root, vector<int>& lst) {if (root == nullptr) return;traverse(root->left, lst);//中序遍历lst.push_back(root->val);traverse(root->right, lst);}public:vector<int> findMode(TreeNode* root) {vector<int> lst;traverse(root, lst);//记录前一个元素值int pre = lst[0];//记录次数int cnt = 1;//记录最大次数int maxCnt = 1;//记录结果vector<int> res;res.push_back(lst[0]);for (size_t i = 1; i < lst.size(); i++) {//如果与前一个节点的值相等if (pre == lst[i]) cnt += 1;else cnt = 1;//如果与最大次数相同，将值放入 resif (cnt == maxCnt) res.push_back(lst[i]);// 如果大于最大次数else if (cnt > maxCnt) {//更新最大次数maxCnt = cnt;//重新更新 resres.clear();res.push_back(lst[i]);}pre = lst[i];}return res;}
};

该算法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

迭代法

同理，利用栈的数据结构，从根节点开始，一层层地遍历，找到左子树最左的那个节点，从它开始处理节点。注意，在迭代法中，我们是一边弹出节点一边维护众数的，具体思路如下：

• 比较当前弹出的节点 cur 与前一个节点 pre :
• • 如果 cur->val == pre->val ，cnt = cnt + 1 。
• • 如果 cur->val > pre->val ，cnt = 1 。
• 比较当前元素重复的次数 cnt 与 maxCnt ：
• • 如果 cnt == maxCnt ，说明当前的元素值 cur->val 出现的次数等于当前众数出现的次数，将 cur->val 加入 res 。
• • 如果 cnt > maxCnt ，说明当前的元素值 cur->val 出现的次数大于当前众数出现的次数，所以 将 maxCnt 更新为 cnt ，清空 res ，之后将 cur->val 加入 res 。

class Solution {
public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> stk;TreeNode* pre = nullptr;//记录次数int cnt = 0;//记录最大次数int maxCnt = 0;//记录结果vector<int> res;while (!stk.empty() || root != nullptr) {//一直向左子树走，每一次将当前节点保存到栈中if (root != nullptr) {stk.push(root);root = root->left;}//当前节点为空，证明走到了最左边，从栈中弹出节点//开始对右子树重复上述过程else {TreeNode* cur = stk.top();stk.pop();//第一个节点if (pre == nullptr) cnt = 1;//如果与前一个节点的值相等else if (pre->val == cur->val) cnt += 1;else cnt = 1;//如果和最大次数相同，将值放入 resif (cnt == maxCnt) res.push_back(cur->val);//如果大于最大次数else if (cnt > maxCnt) {//更新最大次数maxCnt = cnt;//重新更新 resres.clear();res.push_back(cur->val);}pre = cur;root = cur->right;}}return res;}
};

LeetCode #701：Insert into a Binary Search Tree 二叉搜索树中的插入操作

给定二叉搜索树的根节点 root 和要插入的数值 value ，将值插入二叉搜索树，返回插入后二叉搜索树的根节点。
输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

二叉搜素树的插入操作，同二叉树的插入一样，将要插入的节点 node 放在树中合适的位置，对于新插入的节点来说，这个「位置」一般都是在叶子节点上。基本逻辑还是先「找」再「改」。

递归法

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) return new TreeNode(val);     //找到空位置插入新节点//去右子树找插入位置if (root->val < val) root->right = insertIntoBST(root->right, val);//去左子树找插入位置if (root->val > val) root->left = insertIntoBST(root->left, val);//返回 root，上层递归会接收返回值作为子节点return root;}
};

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

迭代法

要想实现迭代的方法，我们需要多加一个记录插入节点的父节点 parentNode ，通过它来确认插入节点的具体位置。

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {TreeNode* insertNode = new TreeNode(val);    //如果二叉搜索树为空if (root == nullptr) return insertNode;//存储插入节点的父节点TreeNode* parentNode = nullptr;TreeNode* currentNode = root;//寻找插入节点的父节点while (currentNode != nullptr) {if (val < currentNode->val) {parentNode = currentNode;currentNode = currentNode->left;} else {parentNode = currentNode;currentNode = currentNode->right;}}//如果插入节点的值比父节点的值小，则插入左子树if (val < parentNode->val) parentNode->left = insertNode;//如果插入节点的值比父节点的值大，则插入右子树else parentNode->right = insertNode;return root;}
};

该算法的时间复杂度也为 $O(n)$，由于没有使用额外的空间，空间复杂度为 $O(1)$。

LeetCode #450：Delete Node in a BST 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key ，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜素树（有可能被更新）的根节点的引用。

依然是先「找」再「改」，我们可以对此勾勒出基本代码框架。关键问题在于，删除节点的同时不能破坏二叉搜索树的性质，对此有 3 个情况需要考虑：

1. 待删除节点恰好是叶子节点，可以直接删除。
2. 待删除节点只有一个非空子节点，需要让该子节点接替自身的位置。

实际上，这两种情况可以直接转化为 root->left == nullptr 和 root->right == nullptr 这两种更为通用的条件判断来考虑。对于第 3 种情况：

3. 待删除节点同时有两个非空子节点，我们需要找到右子树的最小节点接替自身的位置，这样既可以保证左子树均小于该子树的根节点，也可以确保右子树均大于该子树的根节点，维护了二叉搜索树的性质。

对于找出右子树的最小值，我们利用 BST 的特性，最左边的节点就是最小的节点，构造 getMin() 函数遍历一遍右子树即可。

具体代码实现如下：

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) {// case 1 & 2if (root->left == nullptr) return root->right;if (root->right == nullptr) return root->left;// case 3//获得右子树最小的节点TreeNode* minNode = getMin(root->right);//删除右子树最小的节点root->right = deleteNode(root->right, minNode->val);//用右子树最小的节点替换 root 节点minNode->left = root->left;minNode->right = root->right;root = minNode;} else if (root->val > key) root->left = deleteNode(root->left, key);else if (root->val < key) root->right = deleteNode(root->right, key);return root;}private:TreeNode* getMin(TreeNode* node) {// BST 最左边的就是最小的while (node->left != nullptr) node = node->left;return node;}
};

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

LeetCode #669：Trim a Binary Search Tree 修剪二叉搜索树

给定二叉搜索树的根节点 root ，以及最小边界 low 和最大边界 high 。通过修剪二叉搜索树，使得所有节点的值在 [low,high] 中，结果返回修剪好的二叉搜索树的新的根节点。
注意：修剪树不应该改变保留在树中的元素的相对结构（即如果没有被移除，原有的父代、子代关系都应当保留）。

换言之，就是「将二叉搜索树在 [low, high] 之外的节点值删掉」这一问题，即所谓的“批量删除”。

递归法

对于原始二叉搜索树的每个节点，存在 3 种情况：

• 当前节点值 < 左边界 low ，此时我们只需要处理右子树，左子树全部删除：

if (root->val < low) return trimBST(root->right, low, high);

• 当前节点值 > 右边界 high 。相应地，我们只考虑左子树，右子树全部删除：

if (root->val > high) return trimBST(root->left, low, high);

• 当前节点值在 [low,high] 之间，根节点不需要修剪，继续递归修剪左右子树：

if (root->val >= low && root->val <= high) {root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);
}

至于 base case ，遍历到空节点直接返回即可。代码实现如下：

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {// 3 casesif (root == nullptr) return nullptr;if (root->val < low) return trimBST(root->right, low, high);if (root->val > high) return trimBST(root->left, low, high);if (root->val >= low && root->val <= high) {root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);}return root;}
};

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

迭代法

一般我们直接用栈模拟递归，但是基于二叉搜索树的有序性，我们可以按照如下思路模拟：

• 找到第 1 个在 [low, high] 之间的节点（这个节点就是新的二叉搜索树的根节点），修剪这个节点的左右子树。
• 先遍历左子树，对于左子树的节点，如果当前节点 cur 的左子树存在且 cur->left->val < 左边界 low ，直接把 cur->left 指向 cur->left->right 节点。
• 再遍历右子树，对于右子树的节点，如果当前节点 cur 的右子树存在且 cur->right->val > 右边界 high ，直接把 cur->right 指向 cur->right->left 节点。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {//找到修剪之后的二叉搜索树的头节点 rootif (root == nullptr) return nullptr;while (root != nullptr && (root->val > high || root->val < low)) {if (root->val > high) root = root->left;else root = root->right;            }TreeNode* cur = root;//修剪 root 的左子树，将小于 low 的节点删除while (cur != nullptr) {while (cur->left != nullptr && cur->left->val < low) cur->left = cur->left->right;cur = cur->left;}//修剪 root 的右子树，将大于 high 的节点删除cur = root;while (cur != nullptr) {while (cur->right != nullptr && cur->right->val > high) cur->right = cur->right->left;cur = cur->right;}return root;}
};

该算法的时间复杂度为 $O(n)$，开辟了常数级的空间，空间复杂度为 $O(1)$。

LeetCode #108：Convert Sorted Array to Binary Search Tree 将有序数组转换为二叉搜索树

给定一个升序数组 nums ，将其转换为一棵高度平衡的二叉搜索树。
高度平衡二叉树是一棵满足「每个节点的左右两个子树高度差的绝对值不超过 1」的二叉树。

我们知道，对二叉搜索树进行中序遍历时，得到的结果是一个有序的序列，那么给出的有序数组 nums 也可以看作是 BST 中序遍历得来的。因此，我们这样构造二叉搜索树：

• 有序数组中间节点为根节点。
• 根节点左侧区间为左子树。
• 根节点右侧区间为右子树。

然而，如果数组包含偶数个元素，中间节点就存在两个，取任意一个均可。

递归法

class Solution {
public:TreeNode* process(const vector<int>& nums, int left, int right) {if (left > right) return nullptr;//找数组中间元素int mid = left + ((right - left) >> 1);//根节点TreeNode* midNode = new TreeNode(nums[mid]);//递归构造左子树midNode->left = process(nums, left, mid - 1);//递归构造右子树midNode->right = process(nums, mid + 1, right);return midNode;}TreeNode* sortedArrayToBST(const vector<int>& nums) {TreeNode* root = process(nums, 0, nums.size() - 1);return root;}
};

该算法时间复杂度为 $O(n)$，每次递归调用都会将问题规模缩小一半（通过找到中间元素并分别处理左右子数组），递归调用的深度与二分查找的深度相同，因此空间复杂度为 $O(\log n)$。

迭代法

我们使用 3 个队列来模拟：

• rootQue 存放遍历的节点
• leftQue 存放左区间的下标
• rightQue 存放右区间的下标

不断地模拟寻找根节点，构造左子树和构造右子树。

class Solution {
public:TreeNode* sortedArrayToBST(const vector<int>& nums) {if (nums.empty()) return nullptr;//初始化根节点TreeNode* root = new TreeNode(0);//队列存放遍历的节点queue<TreeNode*> rootQue;//队列存放左区间下标queue<int> leftQue;//队列存放右区间下标queue<int> rightQue;//初始化 3 个队列rootQue.push(root);leftQue.push(0);rightQue.push(nums.size() - 1);while (!rootQue.empty()) {TreeNode* cur = rootQue.front();rootQue.pop();int left = leftQue.front();leftQue.pop();int right = rightQue.front();rightQue.pop();//找数组中间元素int mid = left + ((right - left) >> 1);//将中间元素值赋值给节点cur->val = nums[mid];//处理左区间if (left < mid) {cur->left = new TreeNode(0);rootQue.push(cur->left);leftQue.push(left);rightQue.push(mid - 1);}//处理右区间if (right > mid) {cur->right = new TreeNode(0);rootQue.push(cur->right);leftQue.push(mid + 1);rightQue.push(right);}}return root;}
};

该算法的时间复杂度为 $O(n)$，由于维护了 3 个队列，空间复杂度为 $O(n)$。

LeetCode #538：Convert BST to Greater Tree 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换成累加树，使每个节点 node 的新值等于原树中大于或等于 node->val 的值之和。

所谓累加树，就是对于每个节点，把那些大于它的节点值累加给它，构成一棵树。我们可以利用二叉搜索树的有序性，通过中序遍历得到有序序列，从数组最右边开始，从右向左把前一个元素的值累加给自己——这个顺序转换在二叉搜索树中，其实就是先找到二叉搜索树中最大的值，也就是整棵二叉搜索树右下角的值。实际上，累加的顺序，其实就是二叉搜索树反着中序遍历来，即遍历的顺序为：右子树、根节点、左子树。

递归法

重复的子问题就是，先遍历右子树，再对根节点进行累加，最后遍历左子树。

class Solution {
private://记录前一个节点的累加值int preSum;void nodeSum(TreeNode* root) {if (root == nullptr) return;//遍历右子树nodeSum(root->right);//对节点值累加root->val += preSum;//更新 preSum 值preSum = root->val;//遍历左子树nodeSum(root->left);}public:TreeNode* bstToGst(TreeNode* root) {preSum = 0;nodeSum(root);return root;}
};

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

迭代法

依然是逆着中序遍历——右子树、操作节点、左子树。

class Solution {
public:TreeNode* bstToGst(TreeNode* root) {if (root == nullptr) return nullptr;//初始化栈stack<TreeNode*> stk;//记录前一个节点的累加值int preSum = 0;TreeNode* cur = root;while (cur != nullptr || !stk.empty()) {//一直向右子树走，每一次将当前节点保存在栈中if (cur != nullptr) {stk.push(cur);cur = cur->right;}//当前节点为空，证明走到了最右边，从栈中弹出节点进行累加操作//开始对左子树重复上述过程else {cur = stk.top();stk.pop();cur->val += preSum;preSum = cur->val;cur = cur->left;}}return root;}
};