本文主要是介绍【算法训练记录——Day23】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Day23——二叉树Ⅸ
- 669.修剪二叉搜索树
- 108.将有序数组转换为二叉搜索树
- 538.把二叉搜索树转换为累加树
今日内容:
● 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;}
这几种遍历还是没玩明白呀
这篇关于【算法训练记录——Day23】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!