【算法训练记录——Day23】

今日内容：

● 669.修剪二叉搜索树
● 108.将有序数组转换为二叉搜索树
● 538.把二叉搜索树转换为累加树
● 总结篇

669.修剪二叉搜索树

思路：主要是要理解如何删除，左子树小于val就要看左子树的右子树，这一步可以直接用左子树的右子树替换左子树。
遍历二叉树
1. low > root->val，返回root->right的处理结果
2. high < root->val 返回root->left的处理结果
3. 其他情况正常处理左右子树。

	TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return root;if(root->val < low) {root = trimBST(root->right, low, high);} else if(root->val > high) {root = trimBST(root->left, low, high);} else {root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);}return root;}

迭代法暂时留着

108.将有序数组转换为二叉搜索树

思路：题本身不难，但是我又卡在了边界判断条件上，缝缝补补才出来，讨厌没有边界感的我！！！
其实还是没搞明白递归结束条件，等会看看题解。。。

	TreeNode* recursion(vector<int>& nums, int left, int right) {if(left > right)return nullptr;int index = left + ((right - left) >> 1);if(index >= nums.size())return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index - 1);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size());}

思考一下，修改了点代码
上面方法的代码之所以越界，是因为当left == right == size的时候，但我的假设是左闭右开，所以sortedArrayToBST传入的是size，因此不能让left==size，并且 node->left = recursion(nums, left, index - 1)传入的right也没必要减1，减1是左闭右闭的思路

	TreeNode* recursion(vector<int>& nums, int left, int right) {// 左闭右开if(left >= right)return nullptr;int index = left + ((right - left) >> 1);// if(index >= nums.size())//     return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size());}

再来个左闭右闭，相等有意义，并且已访问值不再传入

	TreeNode* recursion(vector<int>& nums, int left, int right) {// 左闭右闭if(left > right)return nullptr;int index = left + ((right - left) >> 1);// if(index >= nums.size())//     return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index - 1);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size() - 1);}

好好好，原来刚开始的代码是左闭右闭思路主函数没有减一引起的。

538.把二叉搜索树转换为累加树

思路：二叉搜索树中序遍历结果为递增（左根右），因此将中序遍历结果加入栈，然后遍历栈，修改元素值即可。
有没有一次遍历就修改的方法呢???想想。。除非倒着来，之前说过倒着来就是回溯，难道把中序遍历结果回溯？？？不会，看题解
好好好，把中序结果加入栈再出来，那不就是右根左吗。。。

	TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return root;stack<TreeNode*> st;TreeNode* cur = root;int sum = 0;while(cur != nullptr || !st.empty()) {if(cur != nullptr) {st.push(cur);cur = cur->right;} else {cur = st.top();st.pop();sum += cur->val;cur->val = sum;cur = cur->left;}}return root;}

这几种遍历还是没玩明白呀