内江网站建设新闻,推广哪些app最挣钱,织梦绿色企业网站模板 苗木企业网站源码 dedecms5.7内核,一个网站seo做哪些工作内容修剪二叉搜索树
题目详细#xff1a;LeetCode.669
做这道题之前建议先看视频讲解#xff0c;没有想象中那么复杂#xff1a;代码随想录—修剪二叉搜索树
由题可知#xff0c;需要删除节点值不在区间内的节点#xff0c;所以可以得到三种情况#xff1a;
情况一#…修剪二叉搜索树
题目详细LeetCode.669
做这道题之前建议先看视频讲解没有想象中那么复杂代码随想录—修剪二叉搜索树
由题可知需要删除节点值不在区间内的节点所以可以得到三种情况
情况一root.val low情况二root.val high情况三low root.val high当节点满足情况一和情况二的条件时删除该节点
但被删除节点的子树可能存在值在区间内的节点利用二叉搜索树的特点可得
情况一root.val lowroot左子树上的节点值都比root.val小右子树上的节点值都比root.val大所以满足区间的节点只会在右子树上出现递归修剪其右子树并返回新的子节点情况二root.val highroot左子树上的节点值都比root.val小右子树上的节点值都比root.val大所以满足区间的节点只会在左子树上出现递归修剪其左子树并返回新的子节点情况三low root.val high说明当前节点不需要被删除递归修剪其左右子树返回修剪好的二叉搜索树的新的根节点
Java解法递归
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(null root) return null;// 根据二叉搜索树的特点可知if(root.val low){// 删除节点的右子树中可能存在值在区间内的节点// 返回修剪好的右子树的新的子节点return trimBST(root.right, low, high);}else if(root.val high){// 删除节点的左子树中可能存在值在区间内的节点// 返回修剪好的左子树的新的子节点return trimBST(root.left, low, high);}// else if(root.val low root.val high)// 递归修剪左右子树root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);// 返回修剪好的二叉搜索树的新的根节点return root;}
}将有序数组转换为二叉搜索树
题目详细LeetCode.108
由题可知
数组中的元素是有序排序的转换的结果是为一棵高度平衡的二叉搜索树
要想使结果的二叉树高度平衡
我们可以找中间值根据中间值的下标将数组分为长度相近的两个子数组利用数组有序的特点其划分后的子数组依旧是有序的 左边的数值较小 中间值右边的数值 中间值 所以我们可以将中间值作为根节点左边的数值作为左子树的节点右边的数值作为右子树的节点采用递归按照以上的逻辑不断划分数组和子树当nums无法再分时将空节点或节点返回给上一层接收决定了节点的位置最后返回转换完成的二叉搜索树的根节点
Java解法递归
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length 0) return null;else if(nums.length 1) return new TreeNode(nums[0]);// 计算中间值的位置并划分构建左右子树的子数组int mid nums.length / 2;int[] left_nums Arrays.copyOfRange(nums, 0, mid);int[] right_nums Arrays.copyOfRange(nums, mid1, nums.length);// 最中间的数值作为树的根节点递归构建左右子树TreeNode root new TreeNode(nums[mid]);root.left sortedArrayToBST(left_nums);root.right sortedArrayToBST(right_nums);// 返回构建完成的二叉搜索树的根节点return root;}
}把二叉搜索树转换为累加树
题目详细LeetCode.538
做这道题之前建议先看视频讲解没有想象中那么复杂代码随想录—把二叉搜索树转换为累加树
Java解法递归双指针法
class Solution {int pre 0;public TreeNode convertBST(TreeNode root) {this.inorder(root);return root;}public void inorder(TreeNode cur){if(null cur) return;inorder(cur.right);cur.val this.pre;this.pre cur.val;inorder(cur.left);}
}
