Day32——二叉树专题 妖狐艹你老母 2024-04-01 18:47 80阅读 0赞 #### 文章目录 #### * * * * 28.删除二叉搜索树的节点 * 29.修剪二叉搜索树 * 30.将有序数组转换为二叉搜索树 * 31. 把二叉搜索树转换为累加树 -------------------- ##### 28.删除二叉搜索树的节点 ##### 题目链接:[450. 删除二叉搜索树中的节点 - 力扣(LeetCode)][450. _ - _LeetCode] * 如果目标节点大于当前节点值,则去右子树中删除; * 如果目标节点小于当前节点值,则去左子树中删除; * 如果目标节点就是当前节点,分为以下三种情况: * 其无左子:其右子顶替其位置,删除了该节点; * 其无右子:其左子顶替其位置,删除了该节点; * 其左右子都有:其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替了其位置,并且删除该节点; **左右子树都有的情况**: ![image-20221115090229467][] **代码实现**: class Solution { public TreeNode deleteNode(TreeNode root, int key) { return dfs(root, key); } public TreeNode dfs(TreeNode root, int key){ if(root == null){ return null; } if(root.val > key) root.left = dfs(root.left, key); else if(root.val < key) root.right = dfs(root.right, key); else{ // 当前节点是要删除的节点 if(root.left == null) return root.right;// 情况1:左子树为空 if(root.right == null) return root.left;// 情况2:右子树为空 // 情况3:左右都不为空 TreeNode node = root.right; while(node.left != null){ // 找出右子树最左的节点 node = node.left; } node.left = root.left;// 删除欲删除节点 拼接 root = root.right;// 跟换删除后树的根节点 } // 递归完整结束后 返回根节点 return root; } } ##### 29.修剪二叉搜索树 ##### **题目链接**:[669. 修剪二叉搜索树 - 力扣(LeetCode)][669. _ - _LeetCode] **思路**: * root的元素值为null,直接返回null if(root == null){ return null; } * root.val < low,递归右子树,并返回右子树符合条件的头节点 if(root.val<low){ return dfs(root.right,low,high); } * root.val > high,递归左子树,并返回左子树符合条件的头节点 if(root.val>high){ return dfs(root.left,low,high); } * 接下来将下一层处理完左子树结果赋值给root->left,右子树结果赋值给root->right。最后返回root root.left = dfs(root.left,low,high); root.right = dfs(root.right,low,high); return root; **代码实现**: class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { return dfs(root,low,high); } public TreeNode dfs(TreeNode root, int low, int high){ if(root==null){ return null; } if(root.val<low){ return dfs(root.right,low,high); } if(root.val>high){ return dfs(root.left,low,high); } root.left = dfs(root.left,low,high); root.right = dfs(root.right,low,high); return root; } } ##### 30.将有序数组转换为二叉搜索树 ##### **题目链接**:[108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)][108. _ - _LeetCode] **思路**: * 确定递归终止条件 if(left>right) return null; * 确定单层递归逻辑 int mid = (right + left)/2; TreeNode root = new TreeNode(nums[mid]); root.left = dfs(nums,left,mid-1); root.right = dfs(nums,mid+1,right); return root; **代码实现**: class Solution { public TreeNode sortedArrayToBST(int[] nums) { return dfs(nums,0,nums.length-1); } public TreeNode dfs(int[] nums, int left, int right){ if(left > right){ return null; } int mid = (right + left)/2; TreeNode root = new TreeNode(nums[mid]); root.left = dfs(nums,left,mid-1); root.right = dfs(nums,mid+1,right); return root; } } ##### 31. 把二叉搜索树转换为累加树 ##### 题目链接:[538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)][538. _ - _LeetCode] **思路**: * 递归函数参数以及返回值 定义一个全局变量pre,用来保存cur节点的前一个节点的数值,定义为int型就可以了 int pre = 0; public TreeNode convertBST(TreeNode root) { } * 确定终止条件 if(root==null) return; * 确定单层递归的逻辑 //右中左 dfs(root.right); root.val+=pre; pre = root.val; dfs(root.left); return root; **代码实现**: class Solution { int pre = 0; public TreeNode convertBST(TreeNode root) { return dfs(root); } public TreeNode dfs(TreeNode root){ if(root==null){ return null; } //右中左 dfs(root.right); root.val+=pre; pre = root.val; dfs(root.left); return root; } } [450. _ - _LeetCode]: https://leetcode.cn/problems/delete-node-in-a-bst/ [image-20221115090229467]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dd021ef6a7d545b59bc9894df4fa9e05.png [669. _ - _LeetCode]: https://leetcode.cn/problems/trim-a-binary-search-tree/ [108. _ - _LeetCode]: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/ [538. _ - _LeetCode]: https://leetcode.cn/problems/convert-bst-to-greater-tree/
相关 Day30——二叉树专题 文章目录 22.验证二叉搜索树 23.二叉搜索树的最小绝对差 24.二叉搜索树中的插入 谁借莪1个温暖的怀抱¢/ 2024年04月01日 15:23/ 0 赞/ 63 阅读
还没有评论,来说两句吧...