目錄

一、669. 修剪二叉搜索樹

二、108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

三、538. 把二叉搜索樹轉(zhuǎn)換為累加樹

一、669. 修剪二叉搜索樹

題目鏈接：力扣

文章講解：代碼隨想錄

視頻講解： 你修剪的方式不對，我來給你糾正一下！| LeetCode：669. 修剪二叉搜索樹

題目：

給你二叉搜索樹的根節(jié)點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節(jié)點的值在[low, high]中。修剪樹 不應該?改變保留在樹中的元素的相對結(jié)構 (即，如果沒有被移除，原有的父代子代關系都應當保留)。 可以證明，存在?唯一的答案?。

所以結(jié)果應當返回修剪好的二叉搜索樹的新的根節(jié)點。注意，根節(jié)點可能會根據(jù)給定的邊界發(fā)生改變。

代碼：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:/*TreeNode* trimBST(TreeNode* root, int low, int high) {//沒有很好的利用搜索樹左小右大的特性if (!root) return root;root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);if (root->val < low || root->val > high){if (!root->left) return root->right;else if (!root->right) return root->left;else{TreeNode* new_node = root->left;while(new_node->right) new_node = new_node->right;new_node->right = root->right;root = root->left;}}return root;//遞歸法if(!root) return NULL;if(root->val < low)     return trimBST(root->right, low, high);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;}*///遞歸法TreeNode* trimBST(TreeNode* root, int low, int high) {if (!root) return nullptr;//將根節(jié)點移到合理范圍內(nèi)while (root && (root->val < low || root->val > high))if (root->val < low) root = root->right;else root = root->left;TreeNode *node = root;// 處理左子樹，處理左子樹的過程中，合理繼續(xù)向左（node的右子樹一定合理)，不合理就向右（node的左子樹一定不合理）if(!root) return NULL;for (;node->left;) if(node->left->val < low) node->left = node->left->right;else node = node->left;// 處理右子樹，處理右子樹的過程中，合理繼續(xù)向右（node的左子樹一定合理)，不合理就向左（node的右子樹一定不合理）for (node = root;node->right;)if (node->right->val > high)node->right = node->right->left;else node = node->right;return root;}
};

時間復雜度: O(n)????????????????????????????????????????空間復雜度: O(1)

?：9:13

總結(jié)：1.考慮二叉搜索樹特性，如果root結(jié)點不符合條件，那么左右子樹有一個必不符合條件，另一個可能存在不符合條件的結(jié)點。

? ? ? ? ? ?2.不考慮特性，則要刪除root結(jié)點，則需要參考二叉樹刪除結(jié)點的方法。

二、108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

題目鏈接：力扣

文章講解：代碼隨想錄

視頻講解：構造平衡二叉搜索樹！| LeetCode：108.將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

題目：給你一個整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。
高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

代碼：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* bulid(vector<int>& nums, int begin, int end){if(begin > end) return NULL;int mid = ((end - begin)>>1) + begin;TreeNode* root = new TreeNode(nums[mid]);root->left = bulid(nums, begin, mid-1);root->right = bulid(nums, mid+1, end);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return bulid(nums, 0, nums.size()-1);}
};

時間復雜度: O(n)????????????????????????????????????????空間復雜度: O(logn)

?：4:11

總結(jié)：1.根據(jù)數(shù)組構造二叉樹，考慮分治來遞歸。二叉搜索樹要求順序，則左子樹在root左邊，右子樹在root右邊。平衡二叉樹要求左右結(jié)點數(shù)相近，則root結(jié)點選取mid。

三、538. 把二叉搜索樹轉(zhuǎn)換為累加樹

題目鏈接：力扣

文章講解：代碼隨想錄

視頻講解：普大喜奔！二叉樹章節(jié)已全部更完啦！| LeetCode：538.把二叉搜索樹轉(zhuǎn)換為累加樹

題目：給出二叉 搜索 樹的根節(jié)點，該樹的節(jié)點值各不相同，請你將其轉(zhuǎn)換為累加樹（Greater Sum Tree），使每個節(jié)點 node?的新值等于原樹中大于或等于?node.val?的值之和。
提醒一下，二叉搜索樹滿足下列約束條件：
節(jié)點的左子樹僅包含鍵 小于 節(jié)點鍵的節(jié)點。
節(jié)點的右子樹僅包含鍵 大于 節(jié)點鍵的節(jié)點。
左右子樹也必須是二叉搜索樹。

代碼：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* pre;TreeNode* convertBST(TreeNode* root) {if (!root) return NULL;convertBST(root->right);if (pre) root->val += pre->val;pre = root;convertBST(root->left);return root;}
};

時間復雜度: O(n)????????????????????????????????????????空間復雜度O(n)

?：2:21

總結(jié)：1、觀察知，所謂累計所有比自己大的結(jié)點的值在二叉搜索樹(中序遍歷可變?yōu)橛行驍?shù)組)中，可表現(xiàn)為自身的值加上上一個結(jié)點的值（已經(jīng)累加過）即可。故采用反中序遍歷即從大到小進行累加。

? ? ? ? ?2、迭代法可通過構造線索二叉樹，將空間復雜度壓縮為O(1)。