本文主要是介绍Day25:Leetcode:669. 修剪二叉搜索树 + 108.将有序数组转换为二叉搜索树 + 538.把二叉搜索树转换为累加树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LeetCode:669. 修剪二叉搜索树
问题描述
解决方案:
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);} else if (root.val > high) {return trimBST(root.left, low, high);} else {root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}
3.复杂度分析
LeetCode:108.将有序数组转换为二叉搜索树
问题描述
解决方案:
1.思路:
- 考虑到是构建高度平衡的搜索二叉树,所以可以总是选择中间位置左边的数字作为根节点;
2.代码实现
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}
3.复杂度分析
LeetCode:538.把二叉搜索树转换为累加树
问题描述
解决方案:
1.思路:
2.代码实现
public TreeNode convertBST(TreeNode root) {if (root != null) {convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);}return root;
}
3.复杂度分析
这篇关于Day25:Leetcode:669. 修剪二叉搜索树 + 108.将有序数组转换为二叉搜索树 + 538.把二叉搜索树转换为累加树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!