题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
<?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param pRoot TreeNode类 * @return bool布尔型 */ function IsBalanced_Solution( $pRoot ) { if($pRoot == null){ return true; } return getHeight($pRoot) == -1 ? false : true; } function getHeight($root){ if($root == null){ return 0; } $left = getHeight($root->left); if($left == -1){ return -1; } $right = getHeight($root->right); if($right == -1 || abs($left - $right)>1){ return -1; } return max($left, $right)+1; }
判断左字数的高度和右子树的高度是否相差1以内,如果从root开始遍历的话,求左子树和右子树的高度,会遍历两遍。
可以从底层开始向上遍历