平衡二叉树
题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
分析
平衡树(Balance Tree,BT) 指的是:任意节点的左右子树的高度差都小于等于1。
同二叉树的深度所用的后序遍历解法一样,只不过增加了对每个节点的左右子树高度差是否小于等于1
的判断,如果高度差大于1,则直接返回 -1(false)。
代码
<?php
namespace app\index\controller;
class Test
{
/**
* 构建二叉树测试数据
*/
public function test()
{
$pRoot = new TreeNode(1);
$node1 = new TreeNode(2);
$node2 = new TreeNode(3);
$pRoot->right = $node1;
$node1->right = $node2;
$this->IsBalanced_Solution($pRoot); // 调用
}
/**
* 如果递归后返回 -1,则不是平衡二叉树(false)
*/
function IsBalanced_Solution($pRoot)
{
return $this->recursive($pRoot) != -1;
}
/**
* 后序遍历,递归,计算左右子树高度差
*/
function recursive($pRoot)
{
if ($pRoot == NULL) return 0; // 终止递归条件:越过叶子节点
$left = $this->recursive($pRoot->left); // 递归左子树
if ($left == -1) return -1; // 如果不平衡,直接返回 -1
$right = $this->recursive($pRoot->right); // 递归右子树
if ($right == -1) return -1; // 如果不平衡,直接返回 -1
// 如果左右子树高度差符合平衡树要求,则返回树的深度,否则返回 -1
return abs($left - $right) < 2 ? max($left, $right) + 1 : -1;
}
}