# [LeetCode] 108. Convert Sorted Array to Binary Search Tree 把有序数组转成二叉搜索树

2021年09月15日 阅读数：1

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.html

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.java

Example:node

```Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5 ```

1. 若任意节点的左子树不空，则左子树上全部节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上全部节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。less

Java: Recursive

```public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0) {
return null;
}
TreeNode head = helper(num, 0, num.length - 1);
}

public TreeNode helper(int[] num, int low, int high) {
if (low > high) { // Done
return null;
}
int mid = (low + high) / 2;
TreeNode node = new TreeNode(num[mid]);
node.left = helper(num, low, mid - 1);
node.right = helper(num, mid + 1, high);
return node;
}
```

Java: Iterative

```public class Solution {

public TreeNode sortedArrayToBST(int[] nums) {

int len = nums.length;
if ( len == 0 ) { return null; }

// 0 as a placeholder

Deque<Integer>  leftIndexStack  = new LinkedList<Integer>()  {{ push(0);     }};
Deque<Integer>  rightIndexStack = new LinkedList<Integer>()  {{ push(len-1); }};

while ( !nodeStack.isEmpty() ) {
TreeNode currNode = nodeStack.pop();
int left  = leftIndexStack.pop();
int right = rightIndexStack.pop();
int mid   = left + (right-left)/2; // avoid overflow
currNode.val = nums[mid];
if ( left <= mid-1 ) {
currNode.left = new TreeNode(0);
nodeStack.push(currNode.left);
leftIndexStack.push(left);
rightIndexStack.push(mid-1);
}
if ( mid+1 <= right ) {
currNode.right = new TreeNode(0);
nodeStack.push(currNode.right);
leftIndexStack.push(mid+1);
rightIndexStack.push(right);
}
}
}

}　　```

Python:

```class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.sortedArrayToBSTRecu(nums, 0, len(nums))

def sortedArrayToBSTRecu(self, nums, start, end):
if start == end:
return None
mid = start + self.perfect_tree_pivot(end - start)
node = TreeNode(nums[mid])
node.left = self.sortedArrayToBSTRecu(nums, start, mid)
node.right = self.sortedArrayToBSTRecu(nums, mid + 1, end)
return node

def perfect_tree_pivot(self, n):
"""
Find the point to partition n keys for a perfect binary search tree
"""
x = 1
# find a power of 2 <= n//2
# while x <= n//2:  # this loop could probably be written more elegantly :)
#     x *= 2
x = 1 << (n.bit_length() - 1)  # use the left bit shift, same as multiplying x by 2**n-1

if x // 2 - 1 <= (n - x):
return x - 1  # case 1: the left subtree of the root is perfect and the right subtree has less nodes
else:
return n - x // 2  # case 2 == n - (x//2 - 1) - 1 : the left subtree of the root
# has more nodes and the right subtree is perfect.
```

C++:

```class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);
}

private:
TreeNode *sortedArrayToBSTHelper(vector<int> &nums, int start, int end) {
if (start <= end) {
TreeNode *node = new TreeNode(nums[start + (end - start) / 2]);
node->left = sortedArrayToBSTHelper(nums, start, start + (end - start) / 2 - 1);
node->right = sortedArrayToBSTHelper(nums, start + (end - start) / 2 + 1, end);
return node;
}
return nullptr;
}
};　　```

C++:

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
return sortedArrayToBST(num, 0 , num.size() - 1);
}
TreeNode *sortedArrayToBST(vector<int> &num, int left, int right) {
if (left > right) return NULL;
int mid = (left + right) / 2;
TreeNode *cur = new TreeNode(num[mid]);
cur->left = sortedArrayToBST(num, left, mid - 1);
cur->right = sortedArrayToBST(num, mid + 1, right);
return cur;
}
};
```

[LeetCode] 109. Convert Sorted List to Binary Search Tree 把有序链表转成二叉搜索树