LeetCode--Balanced Binary Tree
Problem:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary
tree in which the depth of the two subtrees of every node never differ
by more than 1.
Analysis:
题意:
给定的二进制树,确定它是否是均衡二叉树。
对于这个问题,一个高度平衡二叉树被定义为一种二叉树,其中各节点的两个子树的深度相差不能超过1。
Anwser:
public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
//下面两行可以改为return depth(root)!=-1;
if(depth(root)!=-1) return true;
else return false;
}
public int depth(TreeNode root){
if(root==null) return 0;
int ldep,rdep;
ldep = depth(root.left);
rdep = depth(root.right);
//-----这两行是比求树的高度多出的代码,从这里多加一层判断来满足要求。-----//
if(ldep==-1 || rdep==-1) return -1;
if(Math.abs(ldep-rdep)>1) return -1;
//-------------------------------------------------------------//
else {
return Math.max(ldep,rdep)+1;
}
}
}
还没有评论,来说两句吧...