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

問題連結: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

給予一個二元數, 求找到在樹中, 給予的兩個節點的lowest common ancestor (LCA), 也就是最靠近兩節點的共同"祖父節點"
在維基百科上LCA的解釋如下:
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).”

範例如下圖 
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: 節點3為節點5和節點1的LCA

Example graph (photo credit to Leetcode)

想法:

這題是235. Lowest Common Ancestor of a Binary Search Tree的變形題

在我們看236題之前, 來先看我們怎麼解235題吧! 💪

在第235題之中, 一開始給予的樹是一個二元搜索樹(BST)
因為BST的條件, 因此我們可以光靠節點的值來判斷節點處在左子樹還是右子樹 — 只要node A的值比現在root的值還大, 代表node A就會在root的右子樹中, 反之亦然

假設我們有三個節點: root(樹的起點), 及兩個要找的節點p和q
找到p和q的LCA 只有下面兩個步驟

1. 利用三個節點的值來判斷p和q是不是在root的同一側 (是不是一起在左子樹或右子樹裡面)
   而若p和q在不同側, 代表root 就是我們要找的LCA了
2. 若p和q在root的同個子樹下, 那我們就會把現在的root取代成root的左節點或右節點, 左或右則是取決於他們都在哪個子樹下. 然後重複步驟1

以下為解決第235題 3ms 的程式碼100% —

//Iteration Version ------------------------------------------------
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null)
        {
            if(root.val < p.val && root.val < q.val)
                root = root.right;
            else if(root.val > p.val && root.val > q.val)
                root = root.left;
            else
                return root;
        }
        return null;
    }
//Recursive Version ------------------------------------------------
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val <= root.val && q.val >= root.val)
            return root;
        if(p.val >= root.val && q.val <= root.val)
            return root;
        //then it means they are in the same side
        if(root.val > p.val)
            return lowestCommonAncestor(root.left,p,q);
        else
            return lowestCommonAncestor(root.right,p,q);
        
    }

程式邏輯:

在問題第236題中, 我們必須用不同的策略了 因為我們不能光靠p和q的值就知道他們會不會在左子樹或右子樹, 我們必須真的一個一個去找p和q在哪

因此現在最大的問題就是—我們要怎麼找p和q?

我們每次呼叫method的時候, 都會將root兵分兩路去找p跟q, 各自從左子樹跟右子樹裡面找我們的目標節點, 直到已經沒路可找 或者找到p或q其中一個了

以下列出4 種可能會發生的結果—

1. 若我們無法在左子樹找到任何目標節點, 代表LCA不可能在這裏面, 我們將放棄這條路, 回傳我們在右子樹可以找到的結果
2. 若我們無法在右子樹找到任何目標節點, 代表LCA不可能在這裏面, 我們將放棄這條路, 回傳我們在左子樹可以找到的結果
3. 若我們可以在左子樹及右子樹 都找到目標節點, 代表current root就是我們要找的了!
4. 承1跟2, 若左子樹跟右子樹的結果都是 找不到的話, 我們將回傳null, 代表從root開始的所有節點 都不可能存在目標節點的LCA

以下為4ms的程式碼 贏過100% —

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        if(root.val == p.val || root.val == q.val)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left==null)
            return right;
        if(right==null)
            return left;
        return root;
    }

👷來看我們如何運用下面的例子 利用遞迴呼叫方法來找到LCA

Inputs: 
root = [1,2,3,4,5,6,7,null,null,10,null,12,13]
p = 4
q = 10

p = 4, q = 10

✏️我們將方法名lowestCommonAncestor簡寫為LCA

最一開始呼叫: LCA( 1️⃣, 4️⃣, 🔟) -> right 找不到節點, 回傳 left的結果 2️⃣
— left = LCA( 2️⃣, 4️⃣, 🔟) -> left’ 跟 right’ 都找的到, 代表LCA就是root2️⃣
— — left’ = LCA( 4️⃣, 4️⃣, 🔟) = 4️⃣
— — right’ = LCA( 5️⃣, 4️⃣, 🔟) -> right’’ 找不到節點, 回傳 left’’的結果 🔟
— — — left’’ = LCA( 🔟, 4️⃣, 🔟) = 🔟
— — — right’’ = LCA( null, 4️⃣, 🔟) = null
— right = LCA( 3️⃣, 4️⃣, 🔟) -> left’找不到, 回傳 right’的結果 (null)
— — left’ = LCA( 6️⃣, 4️⃣, 🔟) -> left’’找不到, 回傳right’’的結果 (null)
— — — left’’ = LCA( 1️⃣2️⃣, 4️⃣, 🔟) -> left’’’ 找不到, 回傳right’’’ (null)
— — — — left’’’ = LCA( null, 4️⃣, 🔟) = null
— — — — right’’’ = LCA( null, 4️⃣, 🔟) = null
— — — right’’ = LCA( 1️⃣3️⃣, 4️⃣, 🔟) -> left’’’ 找不到, 回傳right’’’ (null)
— — — — left’’’ = LCA( null, 4️⃣, 🔟) = null
— — — — right’’’ = LCA( null, 4️⃣, 🔟) = null
— — right’ = LCA( 7️⃣, 4️⃣, 🔟) -> left’’找不到, 回傳right’’的結果 (null)
— — — left’’ = LCA( null, 4️⃣, 🔟) = null
— — — right’’ = LCA( null, 4️⃣, 🔟) = null