# 108.Convert Sorted Array to Binary Search Tree

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

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.

Example:

```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```

## 解法：

```  public TreeNode sortedArrayToBST(int[] nums) {
int length = nums.length;
sortedArrayToBST_recursion(0,length-1,nums);
return sortedArrayToBST_recursion(0,length-1,nums);
}

public TreeNode sortedArrayToBST_recursion(int start , int end ,int[] nums){
if(start>end) return null;
int mid = (end + start)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = sortedArrayToBST_recursion(start,mid-1,nums);
node.right = sortedArrayToBST_recursion(mid+1,end,nums);
return node;
}```

# 109.Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

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.

Example:

```Given the sorted linked list: [-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```

## 解法：

``` public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
ListNode pre = null;

while (fast!=null && fast.next !=null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}

if (pre!=null) pre.next =null;

TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(start);
start = slow.next;
root.right = sortedListToBST(start);
return root;
}```

```     public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
ListNode pre = new ListNode(0);
while (fast!=null && fast.next !=null){
pre = pre.next;
slow = slow.next;
fast = fast.next.next;
}

pre.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(start);
start = slow.next;
root.right = sortedListToBST(start);
return root;
}
```

0 条评论

• ### LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the ...

• ### LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

• ### LeetCode 169. Majority Element

思路：数组中有一个数字的出现次数超过一半，也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值，一个是数组...

• ### HDOJ 1004

Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

• ### 【图像处理100问】图像处理之各种像素操作效果（上）

学校把很多考试都放在暑假考了，我们专业有6科，分布在一个月内。又要备赛数学建模，快乐暑假已经被榨干了... ...

• ### 1080 线段树练习

1080 线段树练习 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 一...

• ### Leetcode: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return t...

• ### linux系统编程之进程（三）：exec系列函数和system函数

一、exec替换进程映象 在进程的创建上Unix采用了一个独特的方法，它将进程创建与加载一个新进程映象分离。这样的好处是有更多的余地对两种操作进行管理。当我们创...