剑指 Offer 55 - II. 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

分析

我们每次获取左右节点的最大深度，然后相减要是 <= 1
在递归左右节点

代码

var isBalanced = function(root) {
    if(!root) {
        return true
    }

    let left = dept(root.left);
    let right = dept(root.right);
    return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right)
}

var dept = function(root) {
    if(!root) {
        return 0;
    }

    return Math.max( dept(root.left), dept(root.right) ) + 1
}