669. 修剪二叉搜索樹

這題最開始的想法是復用刪除節點的那題的思路做，需要修改的部分就是要讓程序刪除完一個點后繼續遍歷，因為后續可能還有不符合條件的節點。但這樣想也做復雜了。

這類題其實不用想用什么序遍歷，用哪種方式只是為了更好的達成目的，不要被必須用前中后常用的固定的順序束縛住了。

這題翻譯過來，要做的是找到小于low的節點，刪除該節點及其左子樹，將右子樹連到該節點的父節點；找到大于high的節點，刪除該節點以及它的右子樹，將其左子樹連接到該節點的父節點。

可以將情況分解成以下3類：

在low，high區間內的繼續找左右子樹；

碰到小于low的，繼續在其右子樹上找是否還有不在區間的，最后回溯返回這顆右子樹；

碰到大于high的，繼續在其左子樹上找是否還有不在區間的，最后回溯返回這顆左子樹。

這用什么順序都行，只要能遍歷二叉樹。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr ) return nullptr;if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 尋找符合區間[low, high]的節點return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 尋找符合區間[low, high]的節點return left;}root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子return root;}
};

?這題在力扣平臺上跑有點小問題，如果刪除節點的話會報錯，但在本地的ide上運行是不會有問題的，這應該是平臺的問題。以下是找到的解釋的博客。力扣平臺delete的問題：delete出現內存報錯ERROR: AddressSanitizer: heap-use-after-free on address-CSDN博客

108.將有序數組轉換為二叉搜索樹

這題的收獲是再次提醒我了做題時要統一區間的定義。

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

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

這題的收獲是，不要被學過的知識束縛。一開始想到了，這題轉成數組，從后往前累加即可，但對應到樹上，發現使用學過的前中后怎么都不適合來遍歷。看完題解，才發現還能 右中左 這樣遍歷，被學過的知識鎖住了，其實這很簡單就能想到，左中右 中序遍歷，能從小到大輸出，那么 右中左 則是能從大到小輸出。前提是這是二叉搜索樹。

class Solution {
public:int sum = 0;void traversal(TreeNode* root, int& sum){if(root == nullptr) return;traversal(root->right, sum);sum += root->val;root->val = sum;traversal(root->left, sum);}TreeNode* convertBST(TreeNode* root) {traversal(root, sum);return root;}
};