Leetcode 108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
分析
给定一个有序数组，要求转换为二叉搜索树。
数组是有序的，并且要求二叉树。
这里看到数组是有序的，马上想到二分，但是又不需要完全二分 实现。
再复习二叉搜索树的结构特点：
左边节点的值 < 中间节点的值
left < mid
中间节点的值 < 右节点的值
mid < right
看到这种情况，可以让计算机来帮助我们处理左右半边的节点。
于是，我们可以用递归来进行处理。
递归
-
先递归找到中间节点mid的下标
即mid = left + right >> 1 -
再将
root指向nums[mid] -
接着递归处理左半边
即root.left = fun(nums , left , mid - 1) -
再递归处理右半边
即root.right = fun(nums , mid + 1 , right)
这里很多小伙伴会疑惑为什么这样就可以AC，因为递归到最后的基元情况都是只有一个节点即根节点，不过是依次每次处理好每一层的根节点罢了。
注意
递归要对边界条件进行判断处理
当数组下界下标大于数组上界下标时，返回空，这种情况非法。
ACcode
/*** 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) {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;}
}
喜欢的小伙伴点点关注，我们下期再见✌️