이진 검색 트리 균형 조정

1382. 이진 검색 트리 균형

중간

이진 검색 트리의 루트가 주어지면 동일한 노드 값을 갖는 균형 이진 검색 트리를 반환합니다. 답변이 두 개 이상인 경우 중 하나를 반환하세요.

모든 노드의 두 하위 트리 깊이가 1 이상 다르지 않으면 이진 검색 트리는 균형입니다.

예 1:

• 입력: 루트 = [1,null,2,null,3,null,4,null,null]
• 출력: [2,1,3,null,null,null,4]
• 설명: 이것이 유일한 정답은 아니며, [3,1,4,null,2]도 정답입니다.

예 2:

• 입력: 루트 = [2,1,3]
• 출력: [2,1,3]

제약조건:

• 트리의 노드 수는 [1, 10⁴] 범위에 있습니다.
• 1 <= Node.val <= 10⁵

해결책:

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




연락처 링크


링크드인
깃허브



          

            
  

            
        
위 내용은 이진 검색 트리 균형 조정의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!