Seimbangkan Pokok Carian Binari-tutorial php-php.cn

1382. Seimbangkan Pokok Carian Binari

Sederhana

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

Pohon carian binari adalahseimbangjika kedalaman dua subpokok setiap nod tidak pernah berbeza lebih daripada 1.

Contoh 1:

Balance a Binary Search Tree

Input:akar = [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:

Balance a Binary Search Tree

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

Kekangan:

Bilangan nod dalam pokok 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)); } }Hubungi Pautan
        
         LinkedIn
         GitHub
        
Atas ialah kandungan terperinci Seimbangkan Pokok Carian Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!