15. 合并二叉树
617. 合并二叉树【简单】
迭代：把第二棵树合在第一棵树上，返回第一棵树
class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (root1 == nullptr) return root2; //排除两种极端情况 if (root2 == nullptr) return root1; queue<TreeNode*> q; q.push(root1); q.push(root2); while (!q.empty()) { auto node1 = q.front(); q.pop(); auto node2 = q.front(); q.pop(); node1->val += node2->val; if (node1->left && node2->left) { q.push(node1->left); q.push(node2->left); } else if (node2->left) node1->left = node2->left; //树1左子树没有了 把树2左子树合到树1上 if (node1->right && node2->right) { q.push(node1->right); q.push(node2->right); } else if (node2->right) node1->right = node2->right; //树1右子树没有了 把树2右子树合到树1上 } return root1; } };
递归：
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { //1.确定递归的参数和返回值 if (t1 == nullptr) return t2; //2.确定终止条件 if (t2 == nullptr) return t1; //下面三句代码的顺序可以颠倒 3.确定单层递归逻辑 auto root = new TreeNode(t1->val + t2->val); root->left = mergeTrees(t1->left, t2->left); root->right = mergeTrees(t1->right, t2->right); return root; } };
16. 二叉搜索树
做二叉搜索树的题就是跟中序遍历有关，中序遍历的递归和迭代方法
700. 二叉搜索树中的搜索【简单】
思路一：层序遍历上修改，即迭代法
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if (root == nullptr) return NULL; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node->val == val) { return node; } else { if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return NULL; } };
改进：加上二叉搜索数的特点修改
//二叉搜索树是一个有序数 左<中<右 class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { auto node = root; while (node != nullptr) { if(node->val == val) return node; else if (node->val > val) node = node->left; //结点值>目标值 在左子树 else if (node->val < val) node = node->right; //结点值<目标值 在右子树 } return NULL; //未搜索到，返回 } };
递归：
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { //1.确定递归函数参数和返回值 if (root == nullptr) return NULL; if (root->val == val) return root; //2.确定终止条件 else if (root->val > val) return searchBST(root->left, val); //3.确定单层递归逻辑 else if (root->val < val) return searchBST(root->right, val); return NULL; } };
98. 验证二叉搜索树【中等】
思路：二叉搜索树的中序遍历是一个有序数组
class Solution { public: void inorder(TreeNode* root, vector<int>& res) { if (!root) return; inorder(root->left, res); //左 res.push_back(root->val); //中 inorder(root->right, res); //右 } bool isValidBST(TreeNode* root) { vector<int> res; inorder(root, res); for (int i = 1; i < res.size(); i++) { if (res[i] <= res[i - 1]) return false; } return true; } };
迭代法：模拟中序遍历的迭代
class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; // 记录前一个节点 while (cur != NULL || !st.empty()) { if (cur != NULL) { st.push(cur); cur = cur->left; // 左 } else { cur = st.top(); // 中 st.pop(); if (pre != NULL && cur->val <= pre->val) //多了这句 return false; pre = cur; //保存前一个访问的结点 cur = cur->right; // 右 } } return true; } };
530. 二叉搜索树的最小绝对差【简单】
与上一题很类似，中序遍历成数组，然后遍历数组找到minDistinct
class Solution { public: void inorder(TreeNode* root, vector<int>& res) { if (!root) return; inorder(root->left, res); //左 res.push_back(root->val); //中 inorder(root->right, res); //右 } int getMinimumDifference(TreeNode* root) { vector<int> res; inorder(root, res); int minDistinct = INT_MAX; for(int i = 1; i < res.size(); ++i){ minDistinct = min(minDistinct, res[i] - res[i-1]); } return minDistinct; } };
优化：
class Solution { public: int result = INT_MAX; TreeNode* pre; //记录前一个 void traversal(TreeNode* cur) { //1.确定递归函数参数和返回值 if (cur == nullptr) return; //2.确定终止条件 //3.确定单层递归逻辑 traversal(cur->left); // 左 if (pre != nullptr){ // 中 result = min(result, cur->val - pre->val); } pre = cur; // 记录前一个 traversal(cur->right); // 右 } int getMinimumDifference(TreeNode* root) { traversal(root); return result; } };
迭代：
class Solution { public: int getMinimumDifference(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* cur = root; TreeNode* pre = NULL; int minDistinct = INT_MAX; while (cur != nullptr || !s.empty()) { if (cur != nullptr) { // 指针来访问节点，访问到最底层 s.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） s.pop(); res.push_back(cur->val); // 中 if (pre != NULL) minDistinct = min(minDistinct, cur->val - pre->val); //多了这句 pre = cur; //保存前一个访问的结点 cur = cur->right; // 右 } } return minDistinct; } };
501. 二叉搜索树中的众数【简单】
题目意思：所有众数，不是一个
递归：
class Solution { private: void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历 if (cur == NULL) return ; map[cur->val]++; // 统计元素频率 searchBST(cur->left, map); searchBST(cur->right, map); return ; } bool static cmp (const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; } public: vector<int> findMode(TreeNode* root) { unordered_map<int, int> map; // key:元素，value:出现频率 vector<int> result; if (root == nullptr) return result; searchBST(root, map); // 1.遍历树，统计每个元素的次数 vector<pair<int, int>> vec(map.begin(), map.end()); // 2.map赋值给vector sort(vec.begin(), vec.end(), cmp); // 3.给频率排个序 result.push_back(vec[0].first); for (int i = 1; i < vec.size(); i++) { // 4.众数可能不止一个 // 取最高的放到result数组中 if (vec[i].second == vec[0].second) result.push_back(vec[i].first); else break; } return result; } };
以上是任何树都可以用的方法，没用到二叉搜索树的性质
回顾中序遍历的递归版本：
class Solution { public: void preorder(TreeNode *root, vector<int> &res) { if (root == nullptr) return; preorder(root->left, res); //左 res.push_back(root->val); //中 preorder(root->right, res); //右 } vector<int> preorderTraversal(TreeNode *root) { vector<int> res; preorder(root, res); return res; } };
利用了二叉搜索树特点的递归方法：
class Solution { private: int maxCount; // 最大频率 int count; // 统计频率 TreeNode* pre; vector<int> result; void searchBST(TreeNode* cur) { if (cur == nullptr) return; searchBST(cur->left); // 左 // 中 if (pre == NULL) count = 1; // 第一个节点 else if (pre->val == cur->val) count++; // 与前一个节点数值相同 else count = 1; // 与前一个节点数值不同 pre = cur; // 更新上一个节点 if (count == maxCount) { // 如果和最大值相同，放进result中 result.push_back(cur->val); } else if (count > maxCount) { // 如果计数大于最大值频率 maxCount = count; // 更新最大频率 result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了 result.push_back(cur->val); } searchBST(cur->right); // 右 return; } public: vector<int> findMode(TreeNode* root) { //初始化所有参数 count = 0; maxCount = 0; TreeNode* pre = NULL; // 记录前一个节点 result.clear(); searchBST(root); return result; } };
回顾一下迭代版本中序遍历：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* cur = root; while (cur != nullptr || !s.empty()) { if (cur != nullptr) { // 指针来访问节点，访问到最底层 s.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） s.pop(); res.push_back(cur->val); // 中 cur = cur->right; // 右 } } return res; } };
迭代：
class Solution { public: vector<int> findMode(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; int maxCount = 0; // 最大频率 int count = 0; // 统计频率 vector<int> res; 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; // 与前一个节点数值不同 if (count == maxCount) { // 如果和最大值相同，放进res中 res.push_back(cur->val); } else if (count > maxCount) { // 如果计数大于最大值频率 maxCount = count; // 更新最大频率 res.clear(); // 很关键的一步，不要忘记清空res，之前res里的元素都失效了 res.push_back(cur->val); } pre = cur; cur = cur->right; // 右 } } return res; } };
236. 二叉树的最近公共祖先【中等】
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //1. if (root == q || root == p || root == nullptr) return root; //2.确定终止条件 TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL) return root; else if (left == NULL && right != NULL) return right; else if (left != NULL && right == NULL) return left; else return NULL; // (left == NULL && right == NULL) } };
235. 二叉搜索树的最近公共祖先【简单】
思路一：递归
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root->val > p->val && root->val > q->val) { return lowestCommonAncestor(root->left, p, q); } else if (root->val < p->val && root->val < q->val) { return lowestCommonAncestor(root->right, p, q); } else return root; } };
思路二：迭代
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { int min_val = min(q->val, p->val); int max_val = max(q->val, p->val); while (root) { if (root->val > max_val) root = root->left; else if (root->val < min_val) root = root->right; else return root; } return NULL; } };
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 NULL; } };
701. 二叉搜索树中的插入操作【中等】
题目意思：对二叉搜索树进行插入操作，使得插入后的树还为二叉搜索树
思路：采用插入叶子结点的方法
递归：
class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) return new TreeNode(val); if (root->val > val) root->left = insertIntoBST(root->left, val); if (root->val < val) root->right = insertIntoBST(root->right, val); return root; } };
迭代：
class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) return new TreeNode(val); //空树 TreeNode* pos = root; while (pos != nullptr) { if (val < pos->val) { //val<当前结点 往左走 if (pos->left == nullptr) { pos->left = new TreeNode(val); break; } pos = pos->left; } else { //往右走 if (pos->right == nullptr) { pos->right = new TreeNode(val); break; } pos = pos->right; } } return root; } };
450. 删除二叉搜索树中的节点【中等】
题目意思：删除二叉搜索树中的一个结点，保证删除后的树还是二叉搜索树
递归：
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了 if (root->val == key) { // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点 if (root->left == nullptr && root->right == nullptr) { ///! 内存释放 delete root; return nullptr; } // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点 else if (root->left == nullptr) { auto retNode = root->right; ///! 内存释放 delete root; return retNode; } // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点 else if (root->right == nullptr) { auto retNode = root->left; ///! 内存释放 delete root; return retNode; } // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置 并返回删除节点右孩子为新的根节点. else { TreeNode* cur = root->right; // 找右子树最左面的节点 while(cur->left != nullptr) { cur = cur->left; } cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置 TreeNode* tmp = root; // 把root节点保存一下，下面来删除 root = root->right; // 返回旧root的右孩子作为新root delete tmp; // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧） return root; } } if (root->val > key) root->left = deleteNode(root->left, key); if (root->val < key) root->right = deleteNode(root->right, key); return root; } };
迭代：
class Solution { public: TreeNode* deleteOneNode(TreeNode* target){ //返回删除后的树的头结点 if(target->right == nullptr && target->left == nullptr) return nullptr; else if(target->right == nullptr && target->left != nullptr) return target->left; else if(target->right != nullptr && target->left == nullptr) return target->right; else{ TreeNode* cur = target->right; while(cur->left != nullptr){ cur = cur->left; } cur->left = target->left; return target->right; } } TreeNode* deleteNode(TreeNode* root, int key) { if(root == nullptr) return root; TreeNode* cur = root; TreeNode* pre = nullptr; //记录待删除结点的父亲结点 while(cur != nullptr){ if(key > cur->val){ pre = cur; cur = cur->right; //增大cur的值 } else if(key < cur->val){ pre = cur; cur = cur->left; //缩小cur的值 } else if(key == cur->val){ //找到待删除的结点，作相应的删除操作 if(pre && pre->left == cur){ //删除的是左孩子 pre->left = deleteOneNode(cur); return root; } else if(pre && pre->right == cur){ //删除的是右孩子 pre->right = deleteOneNode(cur); return root; } else if(pre == nullptr){ //待删除节点刚好是根结点 return deleteOneNode(cur); } } } return root; //未搜索到，返回原树 } };
669. 修剪二叉搜索树【中等】
递归：
class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if (root == nullptr) return nullptr; else if (root->val < low) return trimBST(root->right, low, high); else if (root->val > high) return trimBST(root->left, low, high); root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } };
迭代：
class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if (root == nullptr) return nullptr; //排除空树情况 // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭 while (root != nullptr && (root->val < L || root->val > R)) { if (root->val < L) root = root->right; // 小于L往右走 else root = root->left; // 大于R往左走 } TreeNode *cur = root; // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况 while (cur != nullptr) { while (cur->left && cur->left->val < L) { cur->left = cur->left->right; } cur = cur->left; } cur = root; // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况 while (cur != nullptr) { while (cur->right && cur->right->val > R) { cur->right = cur->right->left; } cur = cur->right; } return root; } };
108. 将有序数组转换为二叉搜索树【简单】
题目意思：有序数组->平衡二叉搜索树。答案不唯一
递归：
class Solution { public: TreeNode* traversal(vector<int>& nums, int left, int right) { //1.确定递归函数参数和返回值 if (left > right) return nullptr; //2.确定终止条件 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; } TreeNode* sortedArrayToBST(vector<int>& nums) { TreeNode* root = traversal(nums, 0, nums.size() - 1); 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); // 0为左区间下标初始位置 rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置 while (!nodeQue.empty()) { auto 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]; // 将mid对应的元素给中间节点 if (left <= mid - 1) { // 处理左区间 curNode->left = new TreeNode(0); nodeQue.push(curNode->left); leftQue.push(left); rightQue.push(mid - 1); } if (right >= mid + 1) { // 处理右区间 curNode->right = new TreeNode(0); nodeQue.push(curNode->right); leftQue.push(mid + 1); rightQue.push(right); } } return root; } };
538. 把二叉搜索树转换为累加树【中等】
思路：反中序遍历
递归：
class Solution { private: int pre; void traversal(TreeNode* cur) { if(cur == nullptr) return; traversal(cur->right); //右 cur->val += pre; //中 pre = cur->val; traversal(cur->left); //左 } public: TreeNode* convertBST(TreeNode* root) { pre = 0; traversal(root); return root; } };
回顾中序遍历：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* cur = root; while (cur != nullptr || !s.empty()) { if (cur != nullptr) { // 指针来访问节点，访问到最底层 s.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） s.pop(); res.push_back(cur->val); // 中 cur = cur->right; // 右 } } return res; } };
**迭代：**就是中序遍历模板题
class Solution { private: int pre; // 记录前一个节点的数值 void traversal(TreeNode* root) { stack<TreeNode*> s; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { if (cur != nullptr) { s.push(cur); cur = cur->right; // 右 } else { cur = s.top(); // 中 s.pop(); cur->val += pre; //做处理 pre = cur->val; cur = cur->left; // 左 } } } public: TreeNode* convertBST(TreeNode* root) { pre = 0; traversal(root); return root; } };
