110. Balanced Binary Tree

解題程式碼

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
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));
};

解題思路、演算法

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

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

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

解法的時間、空間複雜度

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

參考資料

LeetCode 110. Balanced Binary Tree

102. Binary Tree Level Order Traversal

解題程式碼

var levelOrder = function (root) {
  let queue = [root];
  let out = [];

  while (queue[0]) {
    const currQueueLength = queue.length;
    const layerNodes = [];

    for (let i = 0; i < currQueueLength; i++) {
      let cur = queue.shift();
      layerNodes.push(cur.val);

      if (cur.left) queue.push(cur.left);
      if (cur.right) queue.push(cur.right);
    }
    out.push(layerNodes);
  }

  return out;
};

解題思路、演算法

使用 BFS + Queue 解題，每遍歷一層，將當前 queue 裡的節點取出，加入該節點的左、右子節點到 queue 裡面，遍歷完同層後，往下一層遍歷。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

Binary Tree Level Order Traversal | Tree Breadth First Search 基礎概念 1 - Python - LeetCode 102

236. Lowest Common Ancestor of a Binary Tree

解題程式碼

var lowestCommonAncestor = function (root, p, q) {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left !== null && right !== null) return root;
  return left !== null ? left : right;
};

解題思路、演算法

要找出兩個節點的最小共同祖先，可以先分析出現最小共同祖先的情況，並找到 p 和 q 在哪:

1. 如果 p or q 其中之一是整個 tree 的根節點，那自己本身就是最小祖先，回傳是祖先的那個節點。同樣的邏輯可以套用在遞迴的子樹。
2. 若找到 p 和 q 後，發現分別在一個根節點的左右子樹上，那麼該根節點就是最小的共同祖先。例如範例圖中 p、q 為 5、1，共同祖先為 3。p、q 為 6、4，共同祖先為 5。
3. 若在左子樹上沒找到 p 和 q，代表兩者都在右子樹上，回傳右子樹找到的結果。例如 p、q 為 1、0，左子樹(5 根節點的子樹)會回傳 null，所以回傳 1 最為共同祖先。
4. 若在右子樹上沒找到 p 和 q，代表兩者都在左子樹上，回傳左子樹找到的結果。例如 p、q 為 6、4，左子樹(1 根節點的子樹)會回傳 null，經過遞迴後，根節點為 2 的子樹會回傳 4，p、q 都找到了，所以回傳 5 最為共同祖先。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

贾考博 LeetCode 236. Lowest Common Ancestor of a Binary Tree 追本溯源 2

leetcode 中文 | Lowest Common Ancestor of a Binary Tree | Facebook 臉書考題 | Leetcode 236 | Python

Leetcode — 236. Lowest Common Ancestor of a Binary Tree (中文)