题目:Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
判断一个二叉树是否为平衡二叉树
关键：
1 平衡二叉树的每一个节点的子数深度相差小于1
- Example 1
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
return true
- Example 2
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
return true
思路
- 高度平衡二叉树是每一个结点的两个子树的深度差不能超过1
- 那么我们肯定需要一个求各个点深度的函数，然后对每个节点的两个子树来比较深度差
所以获取中间值nums[mid]为根节点root，root.left又是[0,mid]的中间值
同理root.right是[mid,nums.lenght]的中间值
然后采用递归即可得到
解法
function maxDepth(root){
if(!root) return 0
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right))
}
var isBalanced = function(root) {
if(!root) return true
if( Math.abs(maxDepth(root.left)- maxDepth(root.right)) > 1) return false
return isBalanced(root.left) && isBalanced(root.right)
};
按照上面例子就是
1 queue = [3]
2 node = 3, level = [3], queue = []
3 node.left = 9, node.right = 20, queue = [9,20]
下一轮循环
1 queue = [9,20]
2 node = 9,level = [9],queue = [20]
3 node = 20,level = [9,20], queue = []
4 node.left = 15, node.right = 7,queue = [17,7]
再一次下一轮。。。
