Icoding题解

题干

共同祖先

假设二叉树采用二叉链表方式存储， root指向根结点，p所指结点和q所指结点为二叉树中的两个结点，编写一个计算它们的最近的共同祖先，函数定义如下：
BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q);

其中 root 指向二叉树的根结点，p 和 q 分别指向二叉树中的两个结点。
提示：在完成本题时，可利用 path 函数获取p和q两个结点到根结点之间的路径，之后再计算两条公共路径得出最近的共同祖先。path函数及栈相关定义如下：

遍历所使用栈的相关操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool path(BiTNode* root, BiTNode* node, Stack* s);

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

分析

  • 简要分析题干：
    得到距离p和q两个结点最近的结点，换言之，求某 node 到 p、q 路径之和的最小值。可以用path求得两个结点之间是否有路径。
  • 应当注意的问题：
    1. 把树二叉树版块的路径题给做了，可以更方便地理解这道题
    2. 当然，先写这道题也没什么问题，只需要理解清楚path这个函数提供的功能即可：path的底部是根结点，顶部是目标结点
    3. 树的基本概念与操作
    4. 树的遍历
  • 解题思路：
    1. 声明两个栈，用于存放根分别到P、Q的路径
    2. 将两个栈的大小保持一致（看代码更容易理解为什么这么做）
    3. 同时出栈元素并比较出栈元素，第一对相等的就是距离P、Q最近的祖先
      核心的思想就在于，根到某个结点的路径是唯一的，也就是说，根到共同祖先的路径是唯一的。我们通过两个栈存放了根到P、Q的路径，路径的长短可能不一致，但是我们可以通过某些手段，使得两个栈的top齐平，且共同祖先不可能存在于被我们舍弃掉的那部分路径中，否则根到共同祖先的路径是不唯一的！

注释代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
    if (!root || !p || !q) {
        return NULL;
    }

    Stack Path_P;
    Stack Path_Q;
    init_stack(&Path_P);
    init_stack(&Path_Q);

    //如果路径无法找到，则不可能存在共同祖先
    if (!path(root, p, &Path_P))
        return NULL;
    if (!path(root, q, &Path_Q))
        return NULL;

    //使得两个栈的长度齐平，若不在同一水平位置比较，是无法找到共同祖先的
    while(Path_P.top != Path_Q.top) {
        if (Path_P.top > Path_Q.top)
            Path_P.top--;
        else
            Path_Q.top--;
    }

    ElemType Temp_Ptr_P;
    ElemType Temp_Ptr_Q;
    //开始循环一一对比, 直到栈空，所有结点比对完成
    while (!is_empty(&Path_P)) {
        pop(&Path_P, &Temp_Ptr_P);
        pop(&Path_P, &Temp_Ptr_P);
        if (Temp_Ptr_P == Temp_Ptr_Q) {
            return Temp_Ptr_P;
        }
    }

    //每一个比对都没有找到相同的结点，则没有共同祖先
    return false;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q){
    Stack PathP;
    Stack PathQ;
    init_stack(&PathP);
    init_stack(&PathQ);
    
    if(!path(root, p, &PathP)) return NULL;
    if(!path(root, q, &PathQ)) return NULL;
        
    ElemType Temp_P;
    ElemType Temp_Q;
    
    while(PathP.top != PathQ.top)
    {
        if(PathP.top > PathQ.top)
            PathP.top--;
        else
            PathQ.top--;
    }
        
    while(!is_empty(&PathP))
    {
        pop(&PathP, &Temp_P);
        pop(&PathQ, &Temp_Q);
        if(Temp_P == Temp_Q)
            return Temp_P;
    }
    
    return NULL;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。