PHP에서 균형 이진 트리인지 확인하는 방법

이진 트리에는 균형 이진 트리라는 것이 있습니다. 오늘은 해당 트리가 균형 이진 트리인지 판단하는 방법을 소개하겠습니다.

주어진 이진 트리가 높이 균형 이진 트리인지 확인하세요.

이 질문에서 높이 균형 이진 트리는 다음과 같이 정의됩니다. 이진 트리의 각 노드에 대한 왼쪽 하위 트리와 오른쪽 하위 트리 간의 높이 차이의 절대값은 1을 초과하지 않습니다.

예 1:

给定二叉树 [3,9,20,null,null,15,7]
   3
   / \
  9  20
    /  \
   15   7

return true .

예 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

return false .

문제 해결 아이디어

다음은 가장 기본적인 위에서 아래로의 무차별 대입 해결 방법입니다. 각 노드는 하위 트리일 수 있으므로 균형 잡힌 이진 트리인지 확인해야 합니다. 이 방법은 반복 계산이 많이 발생하고 시간 복잡도가 높습니다.

상향식 조기 차단 방법: 이진 트리를 선주문 순회하고 하위 트리의 최대 높이를 아래에서 위로 반환하는 아이디어입니다. "가지치기"되어 바로 위로 돌아옵니다.

하향식 PHP 코드

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
* } 
*/
class Solution {
    /** * @param TreeNode $root * @return Boolean */
    function isBalanced($root) {
        if ($root == null) {
            return true;
        }
        if (abs($this->getHeight($root->left) - $this->getHeight($root->right)) > 1) {
            return false;
        }
        return $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }
    function getHeight($node)
    {
        if($node == NULL)
            return 0;
        return 1 + max($this->getHeight($node->left), $this->getHeight($node->right));
    }}

하향식 PHP 코드:

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
* } 
*/
class Solution {
    /** * @param TreeNode $root * @return Boolean */
    function isBalanced($root) {
        return $this->helper($root) >= 0;
    }
    public function helper($root){
        if($root === null){
            return 0;
        }
        $l = $this->helper($root->left);
        $r = $this->helper($root->right);
        if($l === -1 || $r === -1 || abs($l - $r) > 1) return -1;
            return max($l, $r) +1;
    }}

추천 학습: php 비디오 튜토리얼

위 내용은 PHP에서 균형 이진 트리인지 확인하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!