【問題描述】[簡單]

將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。示例:給定有序數組: [-10,-3,0,5,9],一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：0/ \-3 9/ /-10 5

【解答思路】

時間復雜度：O(N) 空間復雜度：O(logN)

1. 中序遍歷，總是選擇中間位置左邊的數字作為根節點

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;} }

2. 中序遍歷，總是選擇中間位置右邊的數字作為根節點

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 + 1) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;} }

3. 中序遍歷，選擇任意一個中間位置數字作為根節點

class Solution {Random rand = new Random();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 + rand.nextInt(2)) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;} }

【總結】

1.二叉搜索樹的中序遍歷是升序序列

2.給定二叉搜索樹的中序遍歷，不能唯一地確定二叉搜索樹

3.多畫圖 找規律 遍歷所有情況

轉載鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/

總結

以上是生活随笔為你收集整理的[Leetcode][第108题][JAVA][将有序数组转换为二叉搜索树][二分法][递归]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。