✅面试题 04.04. 检查平衡性

[Ray-56]

面试题 04.04. 检查平衡性

题目

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例1：

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

    3
   / \
  9  20
    /  \
   15   7

返回 true

示例2：

给定二叉树 [1,2,2,3,3,null,null,4,4]

         1
        / \
       2   2
     /  \
    3    3
  /  \
 4    4

返回 false

[Ray-56]

递归解

var isBalanced = function(root) {
    if (root == null) return true;
    
    if (Math.abs(getDepth(root.right) - getDepth(root.left)) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
};

function getDepth(node) {
    if (node == null) return 0;
    return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
}