Seimbangkan Pokok Carian Binari

1382. Seimbangkan Pokok Carian Binari

Sederhana

Memandangkan punca pokok carian binari, kembalikan pohon carian binari seimbang dengan nilai nod yang sama. Jika terdapat lebih daripada satu jawapan, kembalikan mana-mana daripadanya.

Pokok carian binari adalah seimbang jika kedalaman dua subpokok setiap nod tidak pernah berbeza lebih daripada 1.

Contoh 1:

• Input: punca = [1,null,2,null,3,null,4,null,null]
• Output: [2,1,3,null,null,null,4]
• Penjelasan: Ini bukan satu-satunya jawapan yang betul, [3,1,4,null,2] juga betul.

Contoh 2:

• Input: akar = [2,1,3]
• Output: [2,1,3]

Kekangan:

• Bilangan nod dalam pepohon adalah dalam julat [1, 10⁴].
• 1 <= Node.val <= 10⁵

Penyelesaian:

/**
 * 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));
    }
}




Pautan Kenalan


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Seimbangkan Pokok Carian Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!