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如何判断是否为平衡二叉树的详细内容...