解題程式碼

解法 1.

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

  if (Math.abs(findDepth(root.left) - findDepth(root.right)) > 1) return false;

  return isBalanced(root.left) && isBalanced(root.right);
};

const findDepth = (root) => {
  if (!root) return 0;

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

解法 2. 效率較好

var isBalanced = function (root) {
  let flag = true;

  const findDepth = (root) => {
    if (!root) return 0;

    let leftDepth = findDepth(root.left);
    let rightDepth = findDepth(root.right);

    if (Math.abs(leftDepth - rightDepth) > 1) flag = false;
    return 1 + Math.max(leftDepth, rightDepth);
  };
  findDepth(root);

  return flag;
};

解題思路、演算法

這題要判斷一個二元樹是否平衡。

平衡二元樹是一種每個節點的左右兩子樹高度差都不超過一的二元樹。

1. 首先先用遞迴求一個根節點的左右子樹深度，若左右子樹相差超過 1，就代表非平衡，回傳 false
2. 若沒相差超過 1，就繼續將其左右子樹進行遞迴，判斷左右子樹是否是平衡樹

解法的時間、空間複雜度

時間複雜度: O(n)，每個節點最多訪問一次
空間複雜度: O(n)

參考資料

LeetCode 110. Balanced Binary Tree