236. Lowest Common Ancestor of a Binary Tree

今天一樣想繼續深入討論關於「遞迴（Recursion）」的議題，遞迴很常搭配鏈結串列或是樹的資料結構一起使用。所以，我們也挑選了一題在樹結構中適合用遞迴的題目來玩玩看。

先看一下題目描述

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

再搭配範例理解題目

• Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

• Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

這個題目要找的是二元樹中兩個節點的「Lowest Common Ancestor（最低共同祖先）」，也就是要找出兩個點的共同上層。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：遞迴法

根據「Lowest Common Ancestor（最低共同祖先）」的定義，我們可以稍微整理出以下規則：

• 當這兩個節點處於不同的左右子樹中時，那麼最低公共祖先節點就是這兩棵左右子樹的根節點
• 當這兩個節點處於同一子樹中，那麼最低公共祖先節點就是這兩個節點中最低的那個節點

第一種解法直接將此規則轉換成遞迴的形式。

用 Python 實作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

也可以用 JavaScript 復刻一次

const lowestCommonAncestor = (root, p, q) => {
  if (!root || root == p || root == q) {
    return root
  }
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left && right) {
    return root
  }
  return left ? left : right
}

方法 ②：Stack

第二種邏輯是用迴圈的方式進行迭代，採用中序遍歷的方式將經歷過的點暫存到一個 Stack 中。直到找到指定的點（p 或 q）時，再將 Stack 中的往回彈出，Stack 中的每一個點都代表路徑（也代表該點的祖先）。所以，我們就可以從 Stack 當中找出 p 跟 q 的 LCS。

用 Python 實作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        visited = None
        stack = []
        while stack or root:
            if root:
                stack.append(root);
                root = root.left;
            else:
                mid = stack[len(stack)-1];
                if mid.right and mid.right != visited:
                    root = mid.right
                else:
                    stack.pop()
                    visited = mid;

                    if p == q: return p
                    if mid == p: p = stack[len(stack)-1]
                    if mid == q: q = stack[len(stack)-1]
                    root = None
             

也可以用 JavaScript 復刻一次

var lowestCommonAncestor = function(root, p, q) {
    let visited = null;
    let stack = [];
    while (stack.length != 0 || root) {
      if (root) {
        stack.push(root);
        root = root.left;
      } else {
        let mid = stack[stack.length-1];
        if (mid.right && mid.right != visited) {
          root = mid.right;
        } else {
          stack.pop();
          visited = mid;

          if (p == q) return p;
          if (mid == p) p = stack[stack.length-1];
          if (mid == q) q = stack[stack.length-1];
          root = null;
        }
      }
    }
};

方法 ③：Set

第三種方法是我們可以分成兩個迴圈，第一個先找出其中一點的所有祖先，然後第二個迴圈去判斷是否有跟第一個點收集到的祖先重複。但是因為要找出最低的，所以必須將點存在 stack 中由下往上找。

用 Python 實作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':


        # 先找第一個點的路徑
        stack = [root]
        visited = set()
        a_ancestors = set()
        idx = 0
        while stack:
            cur=stack.pop()
            if not cur in visited:
                visited.add(cur);
                if cur.right: stack.append(cur.right)
                stack.append(cur);
                if cur.left: stack.append(cur.left);
            else:
                if cur == p or cur ==q:
                    idx = idx + 1
                if idx == 1:
                    a_ancestors.add(cur)
                if idx == 2:
                    a_ancestors.add(cur)
                    break
        
        # 再第一個點的路徑是否重疊
        stack = [root];
        visited = set()
        while stack:
            cur = stack.pop()
            if not cur in visited:
                visited.add(cur)
                if cur.right: stack.append(cur.right)
                if cur.left: stack.append(cur.left)
                stack.append(cur)
            elif cur in a_ancestors:
                return cur

        return None 

也可以用 JavaScript 復刻一次

var lowestCommonAncestor = function(root, p, q) {
    // 先找第一個點的路徑
    let stack = [root];
    let visited = new Set();
    let a_ancestors = new Set();
    let idx=0;
    while(stack.length){
        let cur=stack.pop();
        if(!visited.has(cur)){
            visited.add(cur);
            if(cur.right) stack.push(cur.right)
            stack.push(cur);
            if(cur.left) stack.push(cur.left);
        }else{
            if(cur===p||cur===q){
                idx++;
            }
            if(idx===1){
                a_ancestors.add(cur);
            }
            if(idx===2){
                a_ancestors.add(cur);
                break;
            }
        }
    }
    
    // 再第一個點的路徑是否重疊
    stack = [root];
    visited = new Set();
    while(stack.length){
        let cur=stack.pop();
        if(!visited.has(cur)){
            visited.add(cur);
            if(cur.right) stack.push(cur.right)
            if(cur.left) stack.push(cur.left);
            stack.push(cur);
        }else{
            if(a_ancestors.has(cur)) return cur;
        }
    }
    return null;
};

反思沉澱

這個題目透過三種不同的方法解決樹結構中問題，你應該會發現以前習慣的迴圈迭代到了這題變得很陌生，反而遞迴好像比較好理解對嗎？這題主要想要讓大家感受到「遞迴」與「迭代」在某些問題上的思考差異，有時候遞迴其實也很好用的的。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 235. Lowest Common Ancestor of a Binary Search Tree

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。