108. Convert Sorted Array to Binary Search Tree

Leetcode Tree Depth-first Search

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[] num) {
    return  bst(num, 0, num.length - 1);
}

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