跳到主要内容

110 - 平衡二叉树

题目链接​

题目​

给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1。

思路​

  • 判断每个节点的左右两边的高度差是否超过1，并且递归判断左右两侧节点。
  • 使用深度优先搜索来判断当前节点的高度。
  • 使用一个哈希表来存放每个节点的高度，每次到达一个新的节点，都将他的高度储存在哈希表中，这样可以有效避免重复计算，降低了时间复杂度。
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
  if(!root) {
    return true;
  }

  const leftHeight = layerTraverse(root.left);
  const rightHeight = layerTraverse(root.right);
  return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left) && isBalanced(root.right);
};

const hash = new Map();

function height(root) {
  if(!root) {
    return 0;
  }
  if(hash.has(root)) {
    hash.get(root);
  }
  
  let h = Math.max(height(root.right), height(root.left)) + 1;
  hash.set(root, h);
  return h;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)。哈希表将时间复杂度从O(n2)O(n^2) 降低为 O(n)O(n)。
  • 空间复杂度：O(n)O(n)。