做公众号主页面的有哪些网站,建站收入,怎么自己做个免费网站吗,自己做网站 需要哪些东西代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树 文章链接#xff1a;修剪二叉搜索树 将有序数组转换为二叉搜索树 把二叉搜索树转换为累加树 视频链接#xff1a;修剪二叉搜…代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树 文章链接修剪二叉搜索树 将有序数组转换为二叉搜索树 把二叉搜索树转换为累加树 视频链接修剪二叉搜索树 将有序数组转换为二叉搜索树 把二叉搜索树转换为累加树 目录
代码随想录算法训练营第二十二天 | LeetCode 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
1. LeetCode 669. 修剪二叉搜索树
1.1 思路
1.2 代码
2. LeetCode 108. 将有序数组转换为二叉搜索树
2.1 思路
2.2 代码
3. LeetCode 538. 把二叉搜索树转换为累加树
3.1 思路
3.2 代码 1. LeetCode 669. 修剪二叉搜索树
1.1 思路
在上面450. 删除二叉搜索树中的节点这题中有一种情况我们是把删除节点的右子树返回给删除节点的父节点让父节点直接指向被删节点的右子树。递归函数的参数和返回值就是本题给的函数返回的是修剪完后新的二叉树的根节点参数是root左右边界low和high终止条件如果遍历到null就return null常见误区如果root的值比low小或者比high大就返回null如果按照这样删除那么root的父节点就直接指向空了如果root还有左右孩子就直接无法连接了。正确思路如果发现当前节点的值比左边界小或者比右边界大其右子树是可能符合边界条件的就应该先把右子树接着遍历以下是单层递归的逻辑判断如果root的值比low小就接着向右遍历right函数(root.right, low, high)含义是把被删节点的右子树修剪完以后返回给被删节点的父节点然后返回right这里判断后不能直接return root.right因为root的右子树不一定完全符合题目的边界要求因此需要遍历。判断如果root的值比high大就接着向左遍历left函数(root.left, low, high)含义是把被删节点的左子树修剪完以后返回给被删节点的父节点然后返回left这里判断后不能直接return root.left因为root的左子树不一定完全符合题目的边界要求因此需要遍历。接着就是左root.left函数(root.left, low, high)然后是右root.right函数(root.right, low, high)return root。root在上面处理过了
1.2 代码
//
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root null) {return null;}if (root.val low) {return trimBST(root.right, low, high);}if (root.val high) {return trimBST(root.left, low, high);}// root在[low,high]范围内root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);return root;}
}2. LeetCode 108. 将有序数组转换为二叉搜索树
2.1 思路
关于构造二叉树在106. 从中序与后序遍历序列构造二叉树这题中讲解过整体思路是先选取一个中间节点然后将数组分为左区间和右区间递归遍历左区间构造左子树和遍历右区间构造右子树。本题中也只有选取数组中间的数作为中间节点左区间和右区间数量才相同然后左区间也选中间然后分割左右区间右区间也选中间然后分割左右区间。如果数组长度是偶数中间有两个数其实选哪个都可以只是取靠左的那个数和靠右的那个数构造出来的树结构不一样而已。递归函数的参数和返回值参数是nums数组左边界右边界。返回值就是构造出来的二叉树的根节点。定义区间的时候是左闭右闭还是左闭右开这点要注意很重要我们要全部统一定义这里我定义的是左闭右闭的区间终止条件如果leftright就是一个非法区间了因为我这里定义的是左闭右闭leftright是一个合法区间只是这里是只有一个节点那可能是叶子节点但也符合题意的因此我们就leftright时返回null即可单层递归的逻辑中间节点的位置mid(leftright)/2然后是构造二叉树root新的节点把nums[mid]赋值给它然后root.left函数(nums, left, mid-1)因为是左闭右闭的区间所以mid要减1mid-1这个位置是包含右边界的。这个函数的含义是在这个数组下下标是left和mid-1所构造的二叉树的根节点返回过来给root的左子树然后root.right函数(nums, mid1, right)因为是左闭右闭的区间所以mid要1mid1这个位置是包含左边界的。这个函数的含义是在这个数组下下标是mid1和right所构造的二叉树的根节点返回过来给root的右子树。然后返回root即可
2.2 代码
//
class Solution {public TreeNode sortedArrayToBST(int[] nums) {TreeNode root traversal(nums, 0, nums.length - 1);return root;}// 左闭右闭区间[left, right]private TreeNode traversal(int[] nums, int left, int right) {if (left right) return null;int mid left ((right - left) 1);TreeNode root new TreeNode(nums[mid]);root.left traversal(nums, left, mid - 1);root.right traversal(nums, mid 1, right);return root;}
}
3. LeetCode 538. 把二叉搜索树转换为累加树
3.1 思路
本题的累加方式是右中左也就是反中序遍历按照中序遍历的方式从右开始加就看懂了本题我们要从后往前加如何从最大的节点开始倒序遍历呢也就是右中左。那如何当前节点跟前一个节点相加呢双指针root指向当前节点pre指向前一个节点的值然后逐渐相加逐渐往回遍历递归函数的参数和返回值要先定义一个全局变量int pre0直接定义成值就好不用是节点最开始root是指向最大的节点pre0root.valpre最开始是不变的。定义个新函数返回值void因为本题不需要返回值返回什么参数就是传入根节点终止条件遇到空节点就return了单层递归的逻辑因为是右中左因此先往右遍历travelsal(root.right)然后就是中的逻辑就是root.valpre然后preroot.val就更新pre能让下一次root指向下一个节点时pre能表示root的前一个节点的值然后是再往左遍历travelsal(root.left)。最后return即可
3.2 代码
//
class Solution {int sum;public TreeNode convertBST(TreeNode root) {sum 0;convertBST1(root);return root;}// 按右中左顺序遍历累加即可public void convertBST1(TreeNode root) {if (root null) {return;}convertBST1(root.right);sum root.val;root.val sum;convertBST1(root.left);}
}
