PHP でバランスのとれたバイナリ ツリーかどうかを判断する方法

二分木にはバランス二分木と呼ばれるものがあります。今日はその木がバランスの取れた二分木であるかどうかを判断する方法を紹介しますので、困っている友達は参考にしてください。

二分木が与えられた場合、それが高度にバランスの取れた二分木であるかどうかを判断します。

この質問では、高さバランスの取れた二分木は、二分木の各ノードの左右のサブツリー間の高さの差の絶対値が 1 を超えないものと定義されます。

例 1:

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

true を返します。

例 2:

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

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

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 中国語 Web サイトの他の関連記事を参照してください。