平衡二元搜尋樹

王林
發布: 2024-07-16 19:16:50
原創
552 人瀏覽過

1382。平衡二元搜尋樹

給定二元搜尋樹的根,回傳具有相同節點值平衡二元搜尋樹。如果有多個答案,請回傳其中任何一個

如果每個節點的兩個子樹的深度不超過 1,則二元搜尋樹是平衡

範例1:

Balance a Binary Search Tree

  • 輸入: root = [1,null,2,null,3,null,4,null,null]
  • 輸出: [2,1,3,null,null,null,4]
  • 解釋:這不是唯一的正確答案,[3,1,4,null,2]也是正確的。

範例2:

Balance a Binary Search Tree

  • 輸入: root = [2,1,3]
  • 輸出: [2,1,3]

約束:

  • 樹中的節點數量在 [1, 104] 範圍內。
  • 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中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板