平衡二叉搜索树

1382。平衡二叉搜索树

中

给定二叉搜索树的根，返回具有相同节点值的平衡二叉搜索树。如果有多个答案，请返回其中任何一个。

如果每个节点的两个子树的深度不超过 1，则二叉搜索树是平衡。

示例1：

• 输入： root = [1,null,2,null,3,null,4,null,null]
• 输出： [2,1,3,null,null,null,4]
• 解释：这不是唯一的正确答案，[3,1,4,null,2]也是正确的。

示例2：

• 输入： root = [2,1,3]
• 输出： [2,1,3]

约束：

• 树中的节点数量在 [1, 10⁴] 范围内。
• 1 5

解决方案：

/**
 * 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 TreeNode $root
     * @return TreeNode
     */
    function balanceBST($root) {
        $nums = [];
        $this->inorder($root, $nums);
        return $this->build($nums, 0, count($nums) - 1);
    }

    function inorder($root, &$nums) {
        if ($root == null)
        return;
        $this->inorder($root->left, $nums);
        $nums[] = $root->val;
        $this->inorder($root->right, $nums);
    }

    function build($nums, $l, $r) {
        if ($l > $r)
        return null;
        $m = (int)(($l + $r) / 2);
        return new TreeNode($nums[$m], $this->build($nums, $l, $m - 1), $this->build($nums, $m + 1, $r));
    }
}

联系链接

• 领英
• GitHub

以上是平衡二叉搜索树的详细内容。更多信息请关注PHP中文网其他相关文章！