LeetCode.669 修剪二叉搜索树

题目链接 修剪二叉搜索树

题解

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);if(root.val > high) return trimBST(root.left,low,high);root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}
}

解题思路

这段代码用于修剪二叉搜索树（BST），保留所有节点值不在 [low, high] 范围内的节点，核心思路基于 BST 的特性（左子树值 < 根节点值 < 右子树值），通过递归实现高效修剪：

1. 递归终止条件：若当前节点为空，返回 null（空树无需修剪）。

2. 修剪逻辑：

   • 若当前节点值 < low：说明当前节点及左子树均不符合要求，直接返回右子树的修剪结果。
   • 若当前节点值 > high：说明当前节点及右子树均不符合要求，直接返回左子树的修剪结果。
   • 若当前节点值在范围内：递归修剪左子树和右子树，并更新当前节点的左右指针，最后返回当前节点。

3. 核心原理：利用 BST 的有序性，无需遍历所有节点，通过比较当前节点值与范围的关系，直接舍弃不符合条件的子树，大幅减少计算量。

LeetCode.108 将有序数组转换为二叉搜索树

题目链接 将有序数组转换为二叉搜索树

题解

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums == null) return null;int len = nums.length - 1;return getRoot(nums,0,len);}public TreeNode getRoot(int[] nums,int left,int right){if(left > right) return null;int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = getRoot(nums,left,mid-1);root.right = getRoot(nums,mid + 1,right);return root;}
}

解题思路

这段代码的功能是将有序数组转换为高度平衡的二叉搜索树（BST），核心思路是二分递归：利用有序数组的特性，每次选中间元素作为根节点，递归构建左右子树，确保树的高度平衡。以下是详细拆解：

1. 高度平衡 BST 的要求
   任意节点的左右子树高度差的绝对值不超过 1。由于输入数组是有序的，可通过 “二分法” 确保左右子树节点数量均衡，从而保证高度平衡。

2. 递归构建逻辑

   • 选根节点：取当前数组区间 [left, right] 的中间元素作为根节点（mid = (left + right) / 2），这样左右子树的节点数量差最多为 1。
   • 递归构建左右子树：
     • 左子树：递归处理左半区间 [left, mid-1]。
     • 右子树：递归处理右半区间 [mid+1, right]。
   • 终止条件：当 left > right 时（空区间），返回 null。

3. 代码流程

   • 主函数 sortedArrayToBST：初始化递归，传入数组和完整区间 [0, nums.length-1]。
   • 辅助函数 getRoot：
     • 处理空区间，返回 null。
     • 找中间位置，创建根节点。
     • 递归构建左右子树，连接到根节点。
     • 返回当前构建的子树的根节点。

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

题目链接 把二叉搜索树转换为累加树

题解

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums == null) return null;int len = nums.length - 1;return getRoot(nums,0,len);}public TreeNode getRoot(int[] nums,int left,int right){if(left > right) return null;int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = getRoot(nums,left,mid-1);root.right = getRoot(nums,mid + 1,right);return root;}
}

解题思路

这段代码的功能是将有序数组转换为高度平衡的二叉搜索树（BST），核心思路基于二分递归 + 平衡构建，以下是清晰的解题思路拆解：

1. 问题本质

有序数组 → 高度平衡 BST

• 二叉搜索树（BST）：左子树值 < 根值 < 右子树值
• 高度平衡：任意节点的左右子树高度差 ≤ 1

2. 核心思路

利用有序数组的 “有序性” + 二分法，确保树的高度平衡：

• 选根节点：取当前数组区间的中间元素作为根，这样左右子树的节点数天然均衡（差 ≤ 1）。
• 递归构建：
  • 左子树：递归处理左半区间（[left, mid-1]）。
  • 右子树：递归处理右半区间（[mid+1, right]）。

3. 代码流程

主函数 sortedArrayToBST

• 输入：有序数组 nums。
• 处理：
  • 空数组直接返回 null。
  • 调用 getRoot，传入完整区间 [0, nums.length-1]，启动递归。

辅助函数 getRoot

• 输入：数组 nums、当前区间 [left, right]。
• 处理：
  1. 终止条件：left > right（空区间）→ 返回 null。
  2. 选中间节点：mid = (left + right) / 2，取 nums[mid] 作为根节点值。
  3. 递归构建左右子树：
     • 左子树：root.left = getRoot(nums, left, mid-1)
     • 右子树：root.right = getRoot(nums, mid+1, right)
  4. 返回根节点：构建好的子树的根节点。