108. 将有序数组转换为二叉搜索树

题意：

解题思路：

思路：DFS[O(n)，其中 n 是数组的长度，每个数字只访问一次]
1. 平衡二叉搜索树的特点是左右子树高度差在1内，每个节点左子树小于右子树；
2. BST的中序遍历是升序的，又因为题中要求是高度平衡二叉搜索树，因此可以选择升序序列中间元素作为根节点；
3. 根左边元素一定小于根节点，右边元素则大于根节点，递归左右子树构造平衡二叉树；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        return $this->helper($nums, 0, count($nums) - 1);
    }
    function helper($nums, $left, $right) {
        if ($left > $right) return null;
        $mid = $left + floor(($right - $left) >> 1);
        $node = new TreeNode($nums[$mid]);
        $node->left = $this->helper($nums, $left, $mid - 1);
        $node->right = $this->helper($nums, $mid + 1, $right);
        return $node;
    }
}

GO代码实现：

func sortedArrayToBST(nums []int) *TreeNode {
    return helper(nums, 0, len(nums) - 1)
}
func helper(nums []int, left, right int) *TreeNode {
    if left > right {
        return nil
    }
    mid := (left + right) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = helper(nums, left, mid - 1)
    root.Right = helper(nums, mid + 1, right)
    return root
}