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

leetcode108.把升序数组转换成二叉搜索树

news 来源：原创 2024/9/18 13:58:53

题目描述

[-10,-3,0,5,9] 转换成如下二叉搜索树：

解题的核心原理是：二叉搜索树的中序遍历结果是一个升序数组，所以根节点的数值，也位于数组的中部。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1); //递归}//nums={-10,-3,0,5,9}public TreeNode helper(int[] nums, int left, int right) { //开始结点大于尾结点，返回null，这个null在后续的递归中，其实是叶子结点。if (left > right) {  //比如left是0，right是mid-1=-1//叶子结点是nullreturn null;} // 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2; //mid=(0+4)/2=2//初始化二叉搜索树的根结点，最终返回这个根节点TreeNode root = new TreeNode(nums[mid]);         //helper(nums,0,1)-> root.left是-10//左侧的值都比根节点要小//mid-1是这行代码的关键root.left = helper(nums, left, mid - 1); //helper(nums,3,4)-> root.right是5//右侧的值都比根节点要大root.right = helper(nums, mid + 1, right);return root; //返回二叉搜索树的根节点}
}

执行过程：

nums={-10,-3,0,5,9}
helper(nums,0,4)
mid=2   nums[2]=0 root=0
root.left=helper(nums,0,1)==>( mid=0  nums[0]=-10 root=-10 root.left=helper(nums,0,-1)=null root.right=(nums,1,1) ==> (mid=1, root=nums[1]=-3,root.left=helper(nums,1,0)=null  root.right=helper(nums,2,1)=null))root.right=helper(nums,3,4)==>(left=3,right=4,mid=(3+4)/2=3 nums[3]=4  root=4root.left = helper(nums,3,2)=nullroot.right = helper(nums,4,4)==>{  left=4, right=4,mid=4，root=nums[4]=9root.left=helper(nums,4,3)=nullroot.right=helper(nums,5,4)=null}	
）