2018-08-13 11:29:05
一、Convert Sorted Array to Binary Search Tree
问题描述：
问题求解：
public TreeNode sortedArrayToBST2(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return helper(0, nums.length - 1, nums);
}
private TreeNode helper (int start, int end, int[] nums) {
if (start > end) {
return null;
}
int mid= start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(start, mid - 1, nums);
root.right = helper(mid + 1, end , nums);
return root;
}
二、Convert Sorted List to Binary Search Tree
问题描述：
问题求解：
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode tail) {
if (head == tail) return null;
ListNode mid = getMid(head, tail);
TreeNode root = new TreeNode(mid.val);
root.left = helper(head, mid);
root.right = helper(mid.next, tail);
return root;
}
private ListNode getMid(ListNode head, ListNode tail) {
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
三、Construct Binary Search Tree from Preorder Traversal
问题描述：
问题求解：
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) return null;
return helper(preorder, 0, preorder.length - 1);
}
private TreeNode helper(int[] preorder, int left, int right) {
if (right < left) return null;
if (left == right) {
TreeNode node = new TreeNode(preorder[left]);
node.left = null;
node.right = null;
return node;
}
TreeNode node = new TreeNode(preorder[left]);
int mid = getMid(preorder, left, right);
node.left = helper(preorder, left + 1, mid - 1);
node.right = helper(preorder, mid, right);
return node;
}
private int getMid(int[] nums, int left, int right) {
int res = left + 1;
for (; res <= right; res++) {
if (nums[res] > nums[left]) break;
}
return res;
}