当前位置：首页 > news >正文

二叉树习题其六【力扣】【算法学习day.13】

news 2025/6/23 19:22:28

前言

书接上篇文章二叉树习题其四，这篇文章我们将基础拓展

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.修剪二叉搜索树

题目链接:669. 修剪二叉搜索树 - 力扣（LeetCode）

题面:

基本分析:这题和删除节点思路一样

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int h;int l;public TreeNode trimBST(TreeNode root, int low, int high) {h = high;l = low;return recursion(root);}public TreeNode recursion(TreeNode root){if(root==null)return null;root.left = recursion(root.left);root.right = recursion(root.right);if(root.val>h)return root.left;else if(root.val<l)return root.right;return root;}
}

2.将有序数组转换成二叉搜索树

题目链接:108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

题面:

基本分析:我们每次取数组中间的值作为根节点，将这个过程递归

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int len;int[] arr;public TreeNode sortedArrayToBST(int[] nums) {int n = nums.length;arr = nums;len = n;return recursion(0,n-1);}public TreeNode recursion(int l,int r){if(l>r)return null;int m = (l+r)/2;TreeNode node = new TreeNode(arr[m]);node.left=recursion(l,m-1);node.right = recursion(m+1,r);return node;}
}

3.把二叉搜索树转换为累加树

题目链接:538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

题面：

基本分析:就是遍历

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int s = 0;public TreeNode convertBST(TreeNode root) {dfs(root);return root;}private void dfs(TreeNode node) {if (node == null) {return;}dfs(node.right); s += node.val;node.val = s; dfs(node.left); }
}