Leetcode PHP题解--D95 108. Convert Sorted Array to Binary Search Tree

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;
    }
}

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