Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree
题目
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思路
建立根结点，划分左子树和右子树。递归
解题
c++版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return create(nums,0,nums.size()-1);
}
TreeNode* create(vector<int>&nums,int left,int right){
if(left>right)
return NULL;
int mid=(left+right)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=create(nums,left,mid-1);
root->right=create(nums,mid+1,right);
return root;
}
};
python版1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param num, a list of integers
# @return a tree node
def sortedArrayToBST(self, num):
return self.createTree(num, 0,len(num)-1);
def createTree(self,num,left,right):
if left>right:
return None
mid=(left+right)/2
node=TreeNode(num[mid])
nodeLeft=self.createTree(num,left,mid-1)
nodeRight=self.createTree(num,mid+1,right)
node.left=nodeLeft
node.right=nodeRight
return node
