• 技术文章 >后端开发 >PHP问题

    PHP如何判断是否为平衡二叉树

    醉折花枝作酒筹醉折花枝作酒筹2021-07-09 15:46:36转载106
    在二叉树中,有一种叫做平衡二叉树。今天我们就来介绍一下判断该树是不是平衡二叉树的方法,有需要的小伙伴可以参考一下。

    给定一个二叉树,判断它是否是高度平衡的二叉树。

    本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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中文网其它相关文章!

    声明:本文转载于:何晓东的博客,如有侵犯,请联系admin@php.cn删除
    专题推荐:PHP
    上一篇:PHP如何计算二叉树坡度 下一篇:PHP如何计算数据流中的第K大的元素
    第16期线上培训班

    相关文章推荐

    • php怎么删除文件某一行• php怎么实现勾股定理• php setcookie 报错怎么办• PHP中Direct IO扩展的安装使用• PHP如何计算二叉树坡度

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网