在二叉树中，有一种叫做平衡二叉树。今天我们就来介绍一下判断该树是不是平衡二叉树的方法，有需要的小伙伴可以参考一下。
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7] 3 / 9 20 / 15 7
登录后复制
返回 true 。
立即学习“PHP免费学习笔记（深入）”；
示例 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如何判断是否为平衡二叉树的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2114451.html
