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

LeetCode 二叉搜索树双神题通关！有序数组转平衡 BST + 验证 BST，小白递归一把梭

news 2026/5/29 2:30:14

前言

二叉搜索树（BST）是算法刷题的高频必考知识点！今天给大家带来两道最经典、最基础的 BST 题目，全程用最简单的递归实现，代码干净、思路直白，不用死记硬背，看完就能直接写！
一道教你构建平衡二叉搜索树，一道教你验证一棵树是不是合法 BST，两道题搭配学习，直接拿捏 BST 核心逻辑！

第一题：将有序数组转换为二叉搜索树

🎯 题目要求

给你一个升序排列的数组，把它转换成一棵高度平衡的二叉搜索树。平衡树的规则：每个节点的左右子树高度差不超过 1；BST 的规则：左子树节点值 < 根节点值 < 右子树节点值。

💡 小白秒懂思路

数组已经是升序的了，这简直是送分题！核心逻辑：二分法 + 递归

取数组中间元素作为根节点（保证树平衡）
中间左边的元素 → 递归构建左子树（全是小值）
中间右边的元素 → 递归构建右子树（全是大值）
递归结束，一棵完美的平衡 BST 就建好了！

✅ 完整解题代码

/** * 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 { /** 二叉平衡搜索树，找到中间节点，小的在左，大的在右 */ public TreeNode sortedArrayToBST(int[] nums) { //使用二分法来做，找到中间节点 int left = 0; int right = nums.length - 1; return travle(nums, left, right); } // 递归函数：在[left,right]区间构建子树 public TreeNode travle(int []nums, int left, int right){ // 递归终止条件：区间无效，返回空 if(left > right) return null; //找到中间节点，作为根 int mid = (left + right) / 2; TreeNode node = new TreeNode(nums[mid]); //小的元素构建左子树 node.left = travle(nums, left, mid - 1); //大的元素构建右子树 node.right = travle(nums, mid + 1, right); return node; } }

📝 代码超通俗解析

定义左右指针，锁定当前要处理的数组区间
取中点做根，保证左右子树节点数量均衡，树天然平衡
左区间递归生成左子树，右区间递归生成右子树
满足 BST「左小右大」的规则，一行多余代码都没有！

第二题：验证二叉搜索树

🎯 题目要求

给定一棵二叉树，判断它是否是合法的二叉搜索树。

💡 小白秒懂思路

BST 有一个铁律：中序遍历的结果一定是严格升序的！所以解题方法超级简单：

对树做中序遍历（左→根→右）
把遍历的节点值收集到集合里
遍历集合，判断是不是严格递增
是→合法 BST，否→不合法

✅ 完整解题代码

java

运行

/** * 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 { // 收集中序遍历结果 List<Integer> list = new ArrayList<>(); public boolean isValidBST(TreeNode root) { //直接使用中序遍历,收集所有节点值 travle(root); //遍历集合，若不是升序，返回false for(int i = 0; i < list.size() - 1; i++){ if(list.get(i) >= list.get(i + 1)) return false; } return true; } // 中序遍历：左→根→右 public void travle(TreeNode node){ if(node == null) return ; travle(node.left); list.add(node.val); travle(node.right); } }