PHP中如何检测一棵树是否为平衡二叉树？

本文共计665个文字，预计阅读时间需要3分钟。

在二叉树中，存在一种被称为平衡二叉树的数据结构。今天我们来介绍一种判断该树是否为平衡二叉树的方法。有需要的小伙伴可以参考以下内容。

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

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

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

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

解题思路

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

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