Difficulty: Easy

Related Topics: 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:

  1. Given the sorted array: [-10,-3,0,5,9],
  3. One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
  5.       0
  6.      / \
  7.    -3   9
  8.    /   /
  9.  -10  5

Solution

Language: Java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    /*
    二分查找的步骤就是一颗 BST，所以可以使用二分查找来生成 BST
    NOTE: 通过二分查找生成的 BST 必定平衡的

    二分查找有两种实现方法
    1. https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure
    2. https://en.wikipedia.org/wiki/Binary_search_algorithm#Alternative_procedure

    Leetcode 评测系统使用的是方法二

    private TreeNode buildBST(int[] nums, int lo, int hi) {
        if(lo == hi) return null;

        int mid = lo  + (hi - lo) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(arr, lo, mid);
        root.right = buildBST(arr, mid + 1, hi);

        return root;
    }

    下面使用的的是方法一
    */
    private TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) return null;

        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);

        return root;
    }
}