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中文網其他相關文章！