在二叉树中,有一种叫做平衡二叉树。今天我们就来介绍一下判断该树是不是平衡二叉树的方法,有需要的小伙伴可以参考一下。

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如何判断是否为平衡二叉树的详细内容,更多请关注811轩轩资源网其它相关文章!

声明:本文转载于:何晓东的博客,如有侵犯,请联系admin@php.cn删除

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注