[Day 16] LeetCode 75 - 235. Lowest Common Ancestor of a Binary Search Tree

14th鐵人賽 c leetcode

eric1864

2022-09-28 20:55:53

579 瀏覽

分享至

LeetCode 75 Level 1 - Day 8 Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

題目連結
難易度：Medium

題目敘述

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
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).”

預設函數

/**
 * 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) {

}

題目限制

The number of nodes in the tree is in the range $[2, 10^5]$ .
$-10^5$ <= Node.val <= $10^9$
ll Node.val are unique.
p != q
p and q will exist in the BST.

解題過程及程式碼

本題是 Binary Search Tree 的第二題，題目給一個二元搜尋樹 (Binary Search Tree)和其中的2個節點 p 和 q，要找出 p 和 q 兩個節點的lowest common ancestor。

如下圖Fig.1所示，p = 2, q = 8的 LCA 是6，簡單的辨別就是兩個節點都往root方向走，他們路線交會的節點就是 LCA。

下圖Fig.2所示p = 2, q = 4的lowest common ancestor是2。

解題想法是分別列出 p 和 q 往 root 走的所有父階，再去找出最低的重複項目

程式碼上傳

#define COL 150

int counter;

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    int index_p, index_q;
    int break_flag = 0;
    struct TreeNode* ret;
    struct TreeNode* array_p[COL] = {NULL};
    struct TreeNode* array_q[COL] = {NULL};

    /* 把從p走到root的節點都丟到陣列裡 */
    counter = 0;
    AncestorsNodes(root, p->val, array_p);
    index_p = counter;

    /* 把從q走到root的節點都丟到陣列裡 */
    counter = 0;
    AncestorsNodes(root, q->val, array_q);
    index_q = counter;

    /* 找2個陣列裡最先相同的點 */
    for (int i=0; i<index_p; i++) {
        for (int j=0; j<index_q; j++) {
            if (array_p[i]->val == array_q[j]->val) {
                ret = array_p[i];
                break_flag = 1;
                break;
            }
        }
        if (break_flag == 1) break;
    }
    return ret;
}

int AncestorsNodes(struct TreeNode *root, int target, struct TreeNode **ptr_array) {
    if (root == NULL)
        return 0;
    if (root->val == target) {
        // printf("%d ", root->val);
        ptr_array[counter] = root;
        counter++;
        return 1;
    }
    if (AncestorsNodes(root->left, target, ptr_array) || AncestorsNodes(root->right, target, ptr_array)) {
        // printf("%d ", root->val);
        ptr_array[counter] = root;
        counter++;
        return 1;
    }
    return 0;
}

參考資訊

列出特定節點 target 一直走到 root 的做法

bool AncestorsNodes(struct TreeNode *root, int target) {
    if (root == NULL)
        return false;
    if (root->val == target) {
        printf("%d ", root->val);
        counter++;
        return true;
    }
    if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ) {
        printf("%d ", root->val);
        counter++;
        return true;
    }
    return false;
}