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

---

• 原题连接：108. 将有序数组转换为二叉搜索树

1- 思路

递归-

• 整体思路：①选择一个中间点，依据中间点 ②遍历左区间 构造左子树、③遍历右区间，构造右子树

递归函数

• 1- 参数及返回值
  • 参数为 数组、左区间、右区间，区间选择为 左闭右闭。即 [left,right]
• 2- 终止条件
  • 区间不规范，即 if( left > right ) 则为非法区间，此时 return
• 3- 递归逻辑
  • ① 寻找 mid = (left+right)/2
  • ② 构造当前结点 TreeNode root = new TreeNode(nums[mid]);
  • ③ 构造做子树：root.left = Traversal(nums,left,mid-1);
  • ④ 构造右子树：root.right = Traversal(nums,mid+1,right);

---

2- 实现

⭐108. 将有序数组转换为二叉搜索树——题解思路

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

---

3- ACM 实现

public class buildTree {public static 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;}}public static TreeNode build(int[] nums){// 构造return Traversal(nums,0,nums.length-1);}public static TreeNode Traversal(int[] nums,int left,int right){// 终止条件if(left>right){return null;}int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = Traversal(nums,left,mid-1);root.right = Traversal(nums,mid+1,right);return root;}static List<List<Integer>> res = new ArrayList<>();public static List<List<Integer>> levelOrder(TreeNode root) {if(root==null){return res;}
// 队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();List<Integer> path = new ArrayList<>();while(len>0){TreeNode nowNode = queue.poll();path.add(nowNode.val);if(nowNode.left!=null) queue.offer(nowNode.left);if(nowNode.right!=null) queue.offer(nowNode.right);len--;}res.add(new ArrayList<>(path));}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n  = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n ; i++){nums[i] = sc.nextInt();}TreeNode root = build(nums);levelOrder(root);System.out.println("结果是"+res.toString());}
}