Balancieren Sie einen binären Suchbaum

1382. Balancieren Sie einen binären Suchbaum

Mittel

Gibt bei gegebener Wurzel eines binären Suchbaums einen ausgeglichenen binären Suchbaum mit denselben Knotenwerten zurück. Wenn es mehr als eine Antwort gibt, geben Sie eine davon zurück.

Ein binärer Suchbaum ist ausgeglichen, wenn sich die Tiefe der beiden Teilbäume jedes Knotens nie um mehr als 1 unterscheidet.

Beispiel 1:

• Eingabe: root = [1,null,2,null,3,null,4,null,null]
• Ausgabe: [2,1,3,null,null,null,4]
• Erklärung: Dies ist nicht die einzig richtige Antwort, [3,1,4,null,2] ist auch richtig.

Beispiel 2:

• Eingabe: root = [2,1,3]
• Ausgabe: [2,1,3]

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [1, 10⁴].
• 1 <= Node.val <= 10⁵

Lösung:

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




Kontaktlinks


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonBalancieren Sie einen binären Suchbaum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!