# LeetCode 1483. Kth Ancestor of a Tree Node

contributed by < ddj5523fa >

## 簡介:
1.[Leetcode測試連結](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)

2.此題解題方法在於 Binary lifting (倍增)
> 程式碼解題上，個人寫出來時，像是DP。

3.發現Leetcode上，測試問題:
> memory在free方面，即使有memory 沒被釋放，依然測試通過。

4.改寫了兩個程式碼檔，與原本測驗上程式碼進行比較。

:::danger
注意共筆書寫規範，中英文之間用一個半形空白區隔
:notes: jserv
:::

---

## 解題:
### 一.首先需先建立一個公式:
1.A(X,k)是求X的第k個祖先
2.A(X,0)第0個祖先，也就是自己，所以A(X,0)=X
3.沒有該祖先時候標-1

再來我們可以把A(X,k)拆分:

A(X,k)=A(A(X,t),k-t)，1 <= t < k 。
=>以此func.已知得到了一個DP結構。

### 二.Binary lifting (倍增)
將上述整理出的DP結構給用上，只是每次不再是減1來去往過去尋找，而是以2的t次方。
=>所以此為為何建Tree時候，每個node都是紀錄2的次方的祖先。

------>往下看舉例

### 三.Tree中我們以Worst Case作為例子(也就是Skew_Tree):
表格:
Skew_Tree，以0為root
表格的j格子是紀錄:第2^j個祖先!
|i \\ j|0|1|2|3|4|
|-|-|-|-|-|-|-|
|0|-1|-1|-1|-1|-1|
|1|0|-1|-1|-1|-1|
|2|1|0|-1|-1|-1|
|3|2|1|-1|-1|-1|
|4|3|2|0|-1|-1|
|5|4|3|1|-1|-1|
|6|5|4|2|-1|-1|
|7|6|5|3|-1|-1|
|8|7|6|4|0|-1|
|9|8|7|5|1|-1|
|10|9|8|6|2|-1|

而舉例找 A(10,5) (5的binary=101)
(A(10,5是找10的第5個祖先))
A(10,5)=A(A(10,1),4) ---->[1]
=A(9,4)
=5
以binary來看:
(建立個表格)
|Node|K|Binary|描述|
|-|-|-|-|
|10|5|101|因為101的最小bit為1，所以取1，得上式子[1]|
|9|4|100|因為100最大bit為1，十進位是4，可以查表格直接得5! <得解!>
|5|0|0|

A(5,0)=5 =>在一的時候就整理過的公式。

---
[以上方法之參考網址](https://www.youtube.com/watch?v=Vvk4xjLfk84&feature=emb_logo&ab_channel=HuaHua)

---
## 程式碼:
原版本在測驗四第二題中的程式碼會建立出上方例子的表格。
可以發現最後一Col全-1。因此對程式碼進行改進:

### 法一
改進的地方為第16行與21行。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
    int **parent;
    int max_level;
    int n;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));
    obj->n=n;
    int max_level = 32 - __builtin_clz(n);  //

    for (int i = 0; i < n; i++)
    {
        obj->parent[i] = malloc(max_level * sizeof(int));  //
        memset(obj->parent[i], -1, max_level * sizeof(int));
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];


    for (int i = 0; i < parentSize; i++)
    {
        for (int j = 1; j<max_level; j++)
        {
            if(obj->parent[i][j + (-1)] == -1)
                break;
            else
                obj->parent[i][j] = obj->parent[obj->parent[i][j - 1]][j - 1];

        }

    }
    obj->max_level = max_level; //
    return obj;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->n; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}


int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (1<<i))
            node = obj->parent[node][i];
    return node;
}

int main()
{
    const int n=7;
    //Creating a skew_tree :0->1->2->3->4->->5->6->7->8->9->10.
    //Skew-tree is worst case:
    int *parent;
    parent = calloc(n, sizeof(int));
    parent[0]=-1;
    parent[1]=0;
    parent[2]=0;
    parent[3]=1;
    parent[4]=1;
    parent[5]=2;
    parent[6]=2;
    for(int i=0; i<n; i++)
    {
        //parent[i]=i-1;
        printf("%d\n",parent[i]);
    }

    TreeAncestor *obj=treeAncestorCreate(n,parent,7);
    int anc=treeAncestorGetKthAncestor(obj, 3, 1);
    printf("A(x,k)=%d\n",anc);
    anc=treeAncestorGetKthAncestor(obj, 5, 2);
    printf("A(x,k)=%d\n",anc);
    anc=treeAncestorGetKthAncestor(obj, 6, 3);
    printf("A(x,k)=%d\n",anc);
    treeAncestorFree(obj);
    free(parent);
    return 0;
}

==Bug提醒==
其中在```void treeAncestorFree ```func.裡面，一開始我的struct沒加入int n，因此誤寫成了obj->Maxlevel (如下:)

for (int i = 0; i < obj->Maxlevel; i++)
        free(obj->parent[i]);

此段程式碼與上方完整程式碼的14行malloc地方比較可得知這裡memory並沒有成功全釋放掉!
但是LeetCode的Submit卻是會成功的

### 法二

法一只是省略了最後一Col的空間，但實際上，
建立的Tree可以只需要:

|i |Ancestor
|-|-|
|0|{}|
|1|{0}|
|2|{1,0}|
|3|{2,1}|
|4|{3,2,0}|
|5|{4,3,1}|
|6|{5,4,2}|
|7|{6,5,3}|
|8|{7,6,4,0}|
|9|{8,7,5,1}|
|10|{9,8,6,2}|
空間是呈現一個三角狀。
所以使用了 int max_level = 32 - __builtin_clz(i);
與for迴圈做出空間的省略。
但分析出來，時間有稍多了一點，具體看下個分類的(比較)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
    int **ancestor ;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(const int n,int *parent,int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->ancestor = malloc(n * sizeof(int *));
    obj->ancestor[0] = malloc(1 * sizeof(int));
    obj->ancestor[0][0] = -1;
    for (int i = 1; i < n; i++)
    {
        int max_level = 32 - __builtin_clz(i);
        //printf("i=%d, level=%d\n",i,max_level);
        obj->ancestor[i] = malloc(max_level * sizeof(int));
        memset(obj->ancestor[i], -1, max_level*sizeof(int));
    }

    for (int i = 0; i < parentSize; i++)
        obj->ancestor[i][0] = parent[i];
/*
    for(int i=0; i<n; i++)
      {
          int max_level = 32 - __builtin_clz(i);
          for (int j = 0; j < max_level; j++)
          {
              printf("i=%d,j=%d, ancestor[i][j]=%d\n",i,j,obj->ancestor[i][j]);
          }
      }
*/

    obj->max_level=32 - __builtin_clz(n-1);
    for (int j = 1;; j++)
    {
        if(j>obj->max_level)
            break;
        for (int i = 1; i < parentSize; i++)
        {
            if(obj->ancestor[i][j + (-1)] == -1)
                break;
            if(j<(32 - __builtin_clz(i)))
            {
                obj->ancestor[i][j] = obj->ancestor[i][j -1] == -1
                                      ? -1
                                      : obj->ancestor[obj->ancestor[i][j - 1]][j - 1];
            }
            else
                continue;
        }
    }


/*
    for(int i=0; i<n; i++)
      {
          int max_level = 32 - __builtin_clz(i);
          for (int j = 0; j < max_level; j++)
          {
              printf("i=%d,j=%d, ancestor[i][j]=%d\n",i,j,obj->ancestor[i][j]);
          }
      }

*/
    return obj;


}

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = 32 - __builtin_clz(node);
    for (int i = 0; i < max_level ; ++i)
        if (k & (1<<i))
            node = obj->ancestor[node][i];
    return node;
}



void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->max_level; i++)
        free(obj->ancestor[i]);
    free(obj->ancestor);
    free(obj);
}

int main()
{
    const int n=10000;
    //Creating a skew_tree :0->1->2->3->4->->5->6->7->8->9->10.
    //Skew-tree is worst case:
    int *parent;
    parent = calloc(n, sizeof(int));
    /*parent[0]=-1;
    parent[1]=0;
    parent[2]=0;
    parent[3]=1;
    parent[4]=1;
    parent[5]=2;
    parent[6]=2;
    */
    for(int i=0; i<n; i++)
    {
        parent[i]=i-1;
        //printf("%d\n",parent[i]);
    }

    TreeAncestor *obj=treeAncestorCreate(n,parent,10000);
    /*
    int anc=treeAncestorGetKthAncestor(obj, 3, 1);
    printf("A(x,k)=%d\n",anc);
    anc=treeAncestorGetKthAncestor(obj, 5, 2);
    printf("A(x,k)=%d\n",anc);
    anc=treeAncestorGetKthAncestor(obj, 6, 3);
    printf("A(x,k)=%d\n",anc);
    */
    for(int i=0;i<1000;i++)
    {
	int k=treeAncestorGetKthAncestor(obj, 1000, i);
    	printf("A(1000,%d)=%d\n",i,k);
    }
    treeAncestorFree(obj);
    free(parent);
    return 0;
}

==補充==法二程式碼有記憶體誤用的問題，目前正在Debug!

---
## 程式碼在此:

[GitHub](https://github.com/ddj5523fa/LeetCode_Kth)

---
## 比較:
用Valgrind確認記憶體狀況的比較:

1.Origin:

2.改過的第一版(法一):

2.2法一中 treeAncestorFree Func.有誤但leetcode平台卻測試成功:

3.法二:有某部分的操作不當: