每天进步一点点🤏

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

  • 1234 字

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

题目

1
2
3
4
5
6
7
8
9
10
11
给你一个整数数组 nums ，其中元素已升序排列，请你将其转换为一棵二叉搜索树。

示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
思路:
将数组中间的值作为根节点的值,每次根据数组中间值的下标分割成两个数组进行递归

代码:
class TreeNode
{
    public $val = null;
    /**
     * @var TreeNode|null
     */
    public $left = null;
    /**
     * @var TreeNode|null
     */
    public $right = null;

    function __construct($val = 0, $left = null, $right = null)
    {
        $this->val   = $val;
        $this->left  = $left;
        $this->right = $right;
    }
}

/**
 * @param Integer[] $nums
 *
 * @return TreeNode
 */
function sortedArrayToBST($nums)
{
    return $this->node($nums, 0, count($nums) - 1);
}

public function node($nums, $lo, $hi)
{
    if ($lo > $hi) {
        return null;
    }

    // 获取数组中间的值
    $mid = $lo + intdiv($hi - $lo, 2);

    $root = new TreeNode($nums[$mid]);

    // 递归,左节点从0到mid,右节点从mid到末尾
    $root->left  = $this->node($nums, $lo, $mid - 1);
    $root->right = $this->node($nums, $mid + 1, $hi);

    return $root;
}