二分探索木のバランスを取る

1382年。二分探索木のバランスをとる

中

二分探索木のルートを指定すると、同じノード値を持つバランスの取れた二分探索木を返します。複数の回答がある場合は、いずれかを返します。

すべてのノードの 2 つのサブツリーの深さが 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));
    }
}

連絡先リンク

• LinkedIn
• GitHub

以上が二分探索木のバランスを取るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。