D95 108. Convert Sorted Array to Binary Search Tree

题目链接

108. Convert Sorted Array to Binary Search Tree

题目分析

给定一个顺序数组，将其装换成平衡二叉树。

思路

首先讲数组分成两半，左边的元素为左子树的内容，右边为右子树内容。

中间的元素作为当前节点的值。

若左边的元素个数大于0，则递归该进程。

右边同理。

返回当前节点即可。

最终代码

<?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) {
        $len = count($nums);
        $mid = floor($len/2);
        $leftPart = array_slice($nums, 0, $mid);
        $root = new TreeNode($nums[$mid]);
        $rightPart = array_slice($nums, $mid+1);
        
        if(count($leftPart)){
            $root->left  = $this->sortedArrayToBST($leftPart);
        }
        if(count($rightPart)){
            $root->right  = $this->sortedArrayToBST($rightPart);
        }
        return $root;
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。