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

前言二叉搜索树BST是算法刷题的高频必考知识点今天给大家带来两道最经典、最基础的 BST 题目全程用最简单的递归实现代码干净、思路直白不用死记硬背看完就能直接写一道教你构建平衡二叉搜索树一道教你验证一棵树是不是合法 BST两道题搭配学习直接拿捏 BST 核心逻辑第一题将有序数组转换为二叉搜索树 题目要求给你一个升序排列的数组把它转换成一棵高度平衡的二叉搜索树。平衡树的规则每个节点的左右子树高度差不超过 1BST 的规则左子树节点值 根节点值 右子树节点值。 小白秒懂思路数组已经是升序的了这简直是送分题核心逻辑二分法 递归取数组中间元素作为根节点保证树平衡中间左边的元素 → 递归构建左子树全是小值中间右边的元素 → 递归构建右子树全是大值递归结束一棵完美的平衡 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 { // 收集中序遍历结果 ListInteger 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); } } 代码超通俗解析中序遍历二叉树将节点值按顺序存入集合遍历集合只要出现后一个数 ≤ 前一个数就不是 BST全程无复杂逻辑纯遍历 判断小白也能一遍写对 两道题终极总结口诀记忆有序数组转平衡 BST二分找中点中点做根节点左递归左子树右递归右子树验证二叉搜索树中序遍历收集值严格递增就是对