669 修剪二叉搜索樹

給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節(jié)點(diǎn)的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節(jié)點(diǎn)，所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點(diǎn)。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return root; //如果是空節(jié)點(diǎn)直接返回//如果結(jié)點(diǎn)小于最小結(jié)點(diǎn)，這個肯定要刪，此時看一下右孩子們小不小if(root->val < low) return trimBST(root->right, low, high);//如果結(jié)點(diǎn)大于最大結(jié)點(diǎn)，這個肯定要刪，此時看一下左孩子們大不大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) return nullptr;// 處理頭結(jié)點(diǎn)，讓root移動到[L, R] 范圍內(nèi)，注意是左閉右閉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已經(jīng)在[L, R] 范圍內(nèi)，處理左孩子元素小于L的情況while (cur != nullptr) {while (cur->left && cur->left->val < L) {cur->left = cur->left->right;}cur = cur->left;}cur = root;// 此時root已經(jīng)在[L, R] 范圍內(nèi)，處理右孩子大于R的情況while (cur != nullptr) {while (cur->right && cur->right->val > R) {cur->right = cur->right->left;}cur = cur->right;}return root;}
};

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

將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點(diǎn)?的左右兩個子樹的高度差的絕對值不超過 1。

class Solution {
private:TreeNode* traversal(vector<int>& nums, int left, int right) {if(right < left) return nullptr;//為了保證平衡，新創(chuàng)建的一定是中間頭結(jié)點(diǎn)int middle = (left+right)/2;TreeNode* root = new TreeNode(nums[middle]);root->left = traversal(nums,left,middle-1);root->right = traversal(nums, middle+1,right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums,0,nums.size()-1);}
};

迭代法比較復(fù)雜，這里先記錄一下

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {if (nums.size() == 0) return nullptr;TreeNode* root = new TreeNode(0);   // 初始根節(jié)點(diǎn)queue<TreeNode*> nodeQue;           // 放遍歷的節(jié)點(diǎn)queue<int> leftQue;                 // 保存左區(qū)間下標(biāo)queue<int> rightQue;                // 保存右區(qū)間下標(biāo)nodeQue.push(root);                 // 根節(jié)點(diǎn)入隊(duì)列l(wèi)eftQue.push(0);                    // 0為左區(qū)間下標(biāo)初始位置rightQue.push(nums.size() - 1);     // nums.size() - 1為右區(qū)間下標(biāo)初始位置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];       // 將mid對應(yīng)的元素給中間節(jié)點(diǎn)if (left <= mid - 1) {          // 處理左區(qū)間curNode->left = new TreeNode(0);nodeQue.push(curNode->left);leftQue.push(left);rightQue.push(mid - 1);}if (right >= mid + 1) {         // 處理右區(qū)間curNode->right = new TreeNode(0);nodeQue.push(curNode->right);leftQue.push(mid + 1);rightQue.push(right);}}return root;}
};

?538 二叉搜索樹轉(zhuǎn)換為累加樹

class Solution {
private:int pre = 0; // 記錄前一個節(jié)點(diǎn)的數(shù)值void traversal(TreeNode* cur) { // 右中左遍歷if (cur == NULL) 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 {
private:int pre; // 記錄前一個節(jié)點(diǎn)的數(shù)值void traversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->right;   // 右} else {cur = st.top();     // 中st.pop();cur->val += pre;pre = cur->val;cur = cur->left;    // 左}}}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};

?二叉樹，就此完結(jié)！