网站会员注册怎么做,上海市场监督管理局,室内装修设计软件下载,网站建设哪家技术好Day23——二叉树Ⅸ 669.修剪二叉搜索树108.将有序数组转换为二叉搜索树538.把二叉搜索树转换为累加树 今日内容#xff1a; ● 669.修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇
669.修剪二叉搜索树 思路#xff1a;主要是… 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(vectorint 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(vectorint nums) {return recursion(nums, 0, nums.size());}思考一下修改了点代码 上面方法的代码之所以越界是因为当left right size的时候但我的假设是左闭右开所以sortedArrayToBST传入的是size因此不能让leftsize并且 node-left recursion(nums, left, index - 1)传入的right也没必要减1减1是左闭右闭的思路 TreeNode* recursion(vectorint 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(vectorint nums) {return recursion(nums, 0, nums.size());}再来个左闭右闭相等有意义并且已访问值不再传入 TreeNode* recursion(vectorint 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(vectorint nums) {return recursion(nums, 0, nums.size() - 1);}好好好原来刚开始的代码是左闭右闭思路主函数没有减一引起的。
538.把二叉搜索树转换为累加树 思路二叉搜索树中序遍历结果为递增左根右因此将中序遍历结果加入栈然后遍历栈修改元素值即可。 有没有一次遍历就修改的方法呢???想想。。除非倒着来之前说过倒着来就是回溯难道把中序遍历结果回溯不会看题解 好好好把中序结果加入栈再出来那不就是右根左吗。。。 TreeNode* convertBST(TreeNode* root) {if(root nullptr) return root;stackTreeNode* 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;}这几种遍历还是没玩明白呀
