236. Lowest Common Ancestor of a Binary Tree.md

236. Lowest Common Ancestor of a Binary Tree

問題描述

給定一個二元樹，所有的node的value皆不同，請找出p, q兩個node的lowest common ancestor (LCA)。

想法

核心想法:

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

假設要找node(7)和node(4):
從 root(3) 開始 ➔ 不是 7 也不是 4 ➔ 繼續往左右找。
遞迴往左子樹 5 ➔ 不是 7 也不是 4 ➔ 繼續往左右找。
左子樹的左子樹 6 ➔ 不是 7 也不是 4
6 沒有左右子樹 ➔ 回傳 NULL。
左子樹的右子樹 2 ➔ 不是 7 也不是 4 ➔ 繼續往左右找。
左子樹 2 的左子樹 7 ➔ 找到了 7 ➔ 回傳 7。
左子樹 2 的右子樹 4 ➔ 找到了 4！➔ 回傳 4。
到這裡，注意在節點 2 發生什麼事，左子樹回傳 7，右子樹回傳 4，左右都非 NULL ➔ 根據演算法，這裡就是最近公共祖先！
所以在節點 2，left != NULL && right != NULL ➔ 返回節點 2。
然後回到節點 5，左邊是 NULL，右邊收到的是 2（剛剛找出來的），因為只有一邊（右邊）有結果 ➔ 傳右邊（2）上去。
再回到節點 3，左邊收到的是 2，右邊遞迴到 1，但 1 的下面找不到 7 或 4 ➔ 返回 NULL，左邊非 NULL，右邊 NULL ➔ 傳左邊（2）上去，最終答案是節點 2！

程式碼(一)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(!root || root == p || root == q) return root;

    struct TreeNode* left = lowestCommonAncestor(root -> left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root -> right, p, q);

    if(left && right) return root;

    return (left) ? left : right;
}