LeetCode 669 修剪二叉樹

這題用層序遍歷+雙指針刪除不符合條件的節點即可。具體是要用到一個虛擬根節點，雙指針中prev指針每次指向隊列頂元素，cur指針先指向prev左子節點，用循環去除這個位置上不符合條件的節點并連上繼承節點，內部就是一個刪除節點的操作。后指向prev右子節點，重復上述操作。此時若prev左子節點和右子節點仍不為空，則將它們入隊列繼續執行上述過程即可。

后面遇到一個棧溢出錯誤，上網查了資料知道是力扣隱藏的判題代碼求我們將被剪的節點置空，所以又將每次去除后的節點的左子節點和右子節點都賦為nullptr了。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {TreeNode* virtualRoot = new TreeNode(0);virtualRoot->left = root;queue<TreeNode*> myque;myque.push(virtualRoot);while (!myque.empty()) {int num = myque.size();while (num--) {TreeNode* prev = myque.front();TreeNode* cur = prev->left;while (cur && !(cur->val >= low && cur->val <= high)) {if (!cur->left && !cur->right) prev->left = nullptr;else if (!cur->left) {prev->left = cur->right; cur->right = nullptr;} else if (!cur->right) {prev->left = cur->left;cur->left = nullptr;}else {TreeNode* temp = cur->right;while (temp->left) temp = temp->left;temp->left = cur->left;prev->left = cur->right;cur->left = nullptr;cur->right = nullptr;}cur = prev->left;}if (prev->left) myque.push(prev->left);cur = prev->right;while (cur && !(cur->val >= low && cur->val <= high)) {if (!cur->left && !cur->right) prev->right = nullptr;else if (!cur->left) prev->right = cur->right;else if (!cur->right) prev->right = cur->left;else {TreeNode* temp = cur->left;while (temp->right) temp = temp->right;temp->right = cur->right;prev->right = cur->left;}cur->left = nullptr;cur->right = nullptr;cur = prev->right;}if (prev->right) myque.push(prev->right);myque.pop();}}return virtualRoot->left;}
};

LeetCode 108 將有序數組轉化為二叉搜索樹

用遞歸 + 二分查找的思路來處理就行了。

代碼如下：

class Solution {
private:TreeNode* binaryBuild(vector<int>& nums , int l, int r) {if (l > r) return nullptr;int mid = (l + r) / 2;TreeNode* newNode = new TreeNode(nums[mid]);newNode->left = binaryBuild(nums, l, mid - 1);newNode->right = binaryBuild(nums, mid + 1, r);return newNode;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return binaryBuild(nums, 0, nums.size() - 1);}
};

LeetCode 538 把二叉搜索樹轉換為累加樹

迭代法。按照右中左的順序用一個變量依次累加每個節點的值，當到達一個節點時，先把該變量加上該節點的值，之后將該節點的值賦為該變量的值，即可滿足條件。

代碼如下：

class Solution {
public:TreeNode* convertBST(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> mysta;int sum = 0;while (cur || !mysta.empty()) {while (cur) {mysta.push(cur);cur = cur->right;}cur = mysta.top();sum += cur->val;cur->val = sum;mysta.pop();cur = cur->left;}return root;}
};