2020-06-28-PHP 实现判断平衡二叉树

layout: posttitle: PHP 实现判断平衡二叉树
subtitle: PHP 实现判断平衡二叉树
date: 2020-06-28
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 平衡二叉树
- 二叉树
- 递归

判断平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree

解题思路

下面这种是最基础的，自顶到底的暴力求解方法，每个节点都可能是一棵子树，就需要判断是否是平衡的二叉树。此方法会产生大量重复计算，时间复杂度较高。

自底向上的提前阻断法： 思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

自顶向下 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;
    }
}

参考链接： 平衡二叉树

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券