PAT甲级1151LCA in a Binary Tree

Posted on | | Visitors:
Words count in article: 1,336 字 | Reading time ≈ 6 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/1038430130011897856

题解

题目要求

  • 最近公共祖先（LCA，The lowest common ancestor）

    在一颗树中，结点U和V的LCA是U和V为其后代的深度最大的结点。

给定一颗二叉树中的任意两个结点，请找到它们的LCA。

  • 输入

    • M：正整数，不超过1000，需要测试的结点对的数量
    • N：正整数，不超过10000，二叉树中结点的数量，结点值都在int范围内
    • 二叉树中序遍历结果：N个数字
    • 二叉树先序遍历结果：N个数字
    • M个结点对：

  • 输出

    对于每个结点对，判断结点对中每个结点是否存在，如果都存在则找到他们的LCA。

思路

根据先序遍历结果和中序遍历结果可以确定一颗树

中序遍历结果加先序遍历结果可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点。

  1. 使用两个数组分别保存树的先序遍历结果和后序遍历结果

  2. 根据先序遍历结果可以确定根节点

    比如刚开始的第一个结点就是整棵树的根结点

  3. 根据中序遍历结果和整棵树的根结点可以确定整棵树的左右子树

    中序遍历结果中，根结点左侧就是整棵树的左子树的中序遍历结果，根结点右侧就是整棵树的右子树的中序遍历结果

  4. 递归确定左右子树的结构

    某颗树的结构可根据2个变量确定：其根结点在整颗树先序遍历结果中的索引、其中序遍历结果序列（可通过起始索引和结束索引2个变量确定）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void func(int leftPosBoundOfInOrder, int rightPosBoundOfInOrder, int rootPosOfPreOrder){
        /*
        当前这颗树在整棵树中序遍历结果inOrder的范围索引为[leftPosBoundOfInOrder,rightPosBoundOfInOrder]
        rootPosOfPreOrder指当前这颗树根结点在整棵树先序遍历结果preOrder中的索引
        */

        // 越界判断
        if (leftPosBoundOfInOrder > rightPosBoundOfInOrder) return;
        // 左子树
        lca(leftPosBoundOfInOrder, rootPosOfInOrder - 1, rootPosOfPreOrder + 1);
        // 右子树
        lca(rootPosOfInOrder + 1, rightPosBoundOfInOrder, rootPosOfPreOrder + (rootPosOfInOrder - leftPosBoundOfInOrder) + 1);

    }
    func(1, n, 1); // 调用（假设整颗树有n个结点，在数组中的索引为[1,n]）

PAT甲级1138Postorder Traversal这道题也涉及如何根据先序遍历结果和中序遍历结果确定一棵树并遍历它，可以看一看。

最近公共祖先LCA

已知某颗树的根结点，

  1. 若u和u在根结点的左边，则u和v的最近公共祖先在当前子树根结点的左子树寻找；
  2. 如果u和v在当前子树根结点的右边，则u和v的最近公共祖先就在当前子树的右子树寻找；
  3. 如果u和v在当前子树根结点的两边，在当前子树的根结点就是u和v的最近公共祖先；
  4. 如果u或v就是根结点，那其就是这两个结点的最近公共祖先。

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Problem: PAT Advanced 1151
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1038430130011897856
// Tags: Tree LCA Map

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int u, v;
map<int, int> pos;
vector<int> inOrder, preOrder;

void lca(int leftPosBoundOfInOrder, int rightPosBoundOfInOrder, int rootPosOfPreOrder){
    /*
    当前这颗树在整棵树中序遍历结果inOrder的范围索引为[leftPosBoundOfInOrder,rightPosBoundOfInOrder]
    rootPosOfPreOrder指当前这颗树根结点在整棵树先序遍历结果preOrder中的索引
    */
    if (leftPosBoundOfInOrder > rightPosBoundOfInOrder) return; // 越界判断

    int rootPosOfInOrder = pos[preOrder[rootPosOfPreOrder]]; // 根结点在中序遍历结果中的索引
    int uPosOfInorder = pos[u]; // 结点u在中序遍历结果中的索引
    int vPosOfInorder = pos[v]; // 结点v在中序遍历结果中的索引

    // u和v都在左子树就去左子树找
    if (uPosOfInorder < rootPosOfInOrder && vPosOfInorder < rootPosOfInOrder)
        lca(leftPosBoundOfInOrder, rootPosOfInOrder - 1, rootPosOfPreOrder + 1);
    // u和v都在右子树就去右子树找
    else if (uPosOfInorder > rootPosOfInOrder && vPosOfInorder > rootPosOfInOrder)
        lca(rootPosOfInOrder + 1, rightPosBoundOfInOrder, rootPosOfPreOrder + (rootPosOfInOrder - leftPosBoundOfInOrder) + 1);
    // u和v在分别在左右子树，则当前树的根节点就是LCA
    else if ((uPosOfInorder < rootPosOfInOrder && vPosOfInorder > rootPosOfInOrder) || (uPosOfInorder > rootPosOfInOrder && vPosOfInorder < rootPosOfInOrder))
        printf("LCA of %d and %d is %d.\n", u, v, preOrder[rootPosOfPreOrder]);
    // 结点u就是根结点
    else if (uPosOfInorder == rootPosOfInOrder)
        printf("%d is an ancestor of %d.\n", u, v);
    // 结点v就是根结点
    else if (vPosOfInorder == rootPosOfInOrder)
        printf("%d is an ancestor of %d.\n", v, u);
}

int main()
{
    int m, n; // 结点对个数，结点个数
    scanf("%d %d", &m, &n);
    inOrder.resize(n + 1), preOrder.resize(n + 1);

    for (int i = 1; i <= n; i++){ // 记录中序遍历结果，并记录各结点的索引
        scanf("%d", &inOrder[i]);
        pos[inOrder[i]] = i;
    }

    for (int i = 1; i <= n; i++){ // 记录先序遍历结果
        scanf("%d", &preOrder[i]);
    }

    while (m--){
        scanf("%d %d", &u, &v);
        
        if (pos[u] == 0 && pos[v] == 0) // 判断元素是否存在
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if(pos[u] == 0 || pos[v] == 0)
            printf("ERROR: %d is not found.\n", pos[u] == 0 ? u : v);
        else
            lca(1, n, 1);
    }
    return 0;
}

参考链接

https://blog.csdn.net/zhuiqiuzhuoyue583/article/details/80452127

https://blog.csdn.net/liuchuo/article/details/82560863

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!