平衡二元搜尋樹

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中文網其他相關文章！