Day25:Leetcode：669. 修剪二叉搜索树 + 108.将有序数组转换为二叉搜索树 + 538.把二叉搜索树转换为累加树

本文主要是介绍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;
}