Convert Sorted Array to Binary Search Tree, Leetcode 解题笔记

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

非常直接的二分法递归:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        return convert(num, 0, num.length-1);
    }
    
    public TreeNode convert(int[] num, int start, int end){
        if(start > end) return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(num[mid]);
        TreeNode left = convert(num, start, mid-1);
        TreeNode right = convert(num, mid+1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s