PHP怎么判断是否为平衡二叉树
本篇内容介绍了“PHP怎么判断是否为平衡二叉树”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
创新互联公司主要从事网站设计、成都网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务金平,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575
在二叉树中,有一种叫做平衡二叉树。今天我们就来介绍一下判断该树是不是平衡二叉树的方法,有需要的小伙伴可以参考一下。
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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怎么判断是否为平衡二叉树
新闻来源:http://scyanting.com/article/pcgihs.html