day141-LeetCode 110. Balanced Binary Tree

题目

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.

分析

求左右子树的最大深度
即:左右子树的高度差为0

题解

function isBalanceTree (root) {
if (root === null || (root.left === null && root.right === null)) return true
// 分别找出左右子树深度
let deepLeft = findDeepth (root.left)
let deepRight = findDeepth (root.right)
// 是否是平衡树
let isBalance = Math.abs(deepLeft - deepRight) < 1
return isBalance && isBalanceTree(root.left) && isBalanceTree(root.right)
}

function findDeepth (root) {
if (root === null) return 0
let deepLeftDeepth = findDeepth(root.left) + 1
let deepRightDeepth = findDeepth(root.right) + 1

return deepLeftDeepth > deepRightDeepth ? deepLeftDeepth : deepRightDeepth
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/02/2019-06-02/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog