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

思路

二分法(递归)

二叉搜索树是有序的,传入数组也是有序的,有序就要想到二分法。最简单保持树平衡的方式,就是使根节点左右子孙树节点相差不超过1个 (总节点数为奇数时,左右子树节点数相同;为偶数时,左右子树节点数差一)。

二叉搜索树中序遍历的结果,则是一个有序数组。但并不能确定根节点的位置,任何一个点都可能是根节点。当增加了高度平衡这个条件时,有序数组中间位置就可以确定是树的根节点了。以这个思路把有序数组重新构建回二叉搜索树。

复杂度

时间复杂度:O(nlogN)

php 内置函数 array_slice 为n,树构建为logN

空间复杂度:O(n)

递归栈为n

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

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

    function helper($nums, $low, $hight)
    {
        if($low > $hight) return null;

        $mid = intval(($low + $hight) / 2);

        $node = new TreeNode($nums[$mid]);
        $node->left = $this->helper($nums, $low, $mid - 1);
        $node->right = $this->helper($nums, $mid + 1, $hight);

        return $node;
    }
}

results matching ""

    No results matching ""