题解 | #和为S的两个数字#
平衡二叉树
http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
思路：
1. 层序遍历二叉树，挨个判断以该结点为根节点的树是否是平衡二叉树
1）每次循环pop出顶点的结点，并判断是否是平衡二叉树。
2）使用队列存储pop出来结点的子结点
2.如何计算树的高度：递归的方式，返回左右子树的最大值再加1。
import java.util.*;
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null){
return true;
}
LinkedList<TreeNode> queue=new LinkedList<>();//链表模拟队列
queue.addLast(root);//把根结点加入队列。
while(queue.size()>0){
TreeNode node=queue.removeFirst();//队首结点出队列
//如果左右子树高度差大于1，返回false
if(Math.abs(leftHeight(node)-rightHeight(node))>1){
return false;
}
//左右子结点不为空，加入到队列末尾。
if(node.left!=null){
queue.addLast(node.left);
}
if(node.right!=null){
queue.addLast(node.right);
}
}
//如果不存在左右子树高度差大于1的结点，返回true
return true;
}
//计算右子树高度
public int rightHeight(TreeNode node){
if(node.right==null){
return 0;
}
return Height(node.right);
}
//计算左子树高度
public int leftHeight(TreeNode node){
if(node.left==null){
return 0;
}
return Height(node.left);
}
//计算树的高度
public int Height(TreeNode node){
return Math.max(node.left==null?0:Height(node.left),node.right==null?0:Height(node.right))+1;
}
} 
投递阿里国际数字商业集团等公司10个岗位 >
