题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
所有子树都需要满足平衡树性质，因此以下三者使用与逻辑 && 连接；
abs(self.depth(root.left) - self.depth(root.right)) <= 1 ：判断 当前子树 是否是平衡树；
self.isBalanced(root.left) ： 先序遍历递归，判断 当前子树的左子树 是否是平衡树；
self.isBalanced(root.right) ： 先序遍历递归，判断 当前子树的右子树 是否是平衡树；
depth(root) 函数： 计算树 root 的深度
终止条件： 当 root 为空，即越过叶子节点，则返回高度 00 ；
返回值： 返回左 / 右子树的深度的最大值 +1+1 。
abs(self.depth(root.left) - self.depth(root.right)) <= 1 ：判断 当前子树 是否是平衡树；
self.isBalanced(root.left) ： 先序遍历递归，判断 当前子树的左子树 是否是平衡树；
self.isBalanced(root.right) ： 先序遍历递归，判断 当前子树的右子树 是否是平衡树；
depth(root) 函数： 计算树 root 的深度
终止条件： 当 root 为空，即越过叶子节点，则返回高度 00 ；
返回值： 返回左 / 右子树的深度的最大值 +1+1 。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null)
{
return true;
}
return Math.abs(maxDeapth(root.left) - maxDeapth(root.right)) < 2 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int maxDeapth(TreeNode root){
if (root == null){
return 0;
}
return Math.max(maxDeapth(root.left), maxDeapth(root.right)) + 1;
}
}
剑指offer刷题记录 文章被收录于专栏
这个专栏主要记录算法刷题记录 希望对看到的人有所帮助
