<?php 
/** 
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * 后序遍历，然后记录每个节点的深度，然后判断是否平衡
 */
class TreeNode{
    public $val;
    public $left = null;
    public $right = null;
    public function __construct($val){
        $this->val = $val;
    }
}


function isBalance($root)
{
	$depth = 0;
	return isBalanced($root) != -1;
}

function isBalanced($root)
{
	if ($root == null) {
		return 0;
	}
	$left = isBalanced($root->left);
	if ($left == -1) 
		return -1;

	$right = isBalanced($root->right);
	if ($right == -1)
		return -1;

	return abs($right - $left) > 1 ? -1 : 1 + max($right, $left);
}

$node = new TreeNode(1);
$node->right = new TreeNode(2);
$node->left = new TreeNode(3);
$node->right->left = new TreeNode(4); 
$node->right->left->left = new TreeNode(5); 

var_dump(isBalance($node));