PAT甲级|1151 LCA in a Binary Tree 先序中序遍历建树 lca

柔光的暖阳◎ 2021-11-13 19:54 159阅读 0赞

给定先序中序遍历的序列，可以确定一颗唯一的树

## 先序遍历第一个遍历到的是根，中序遍历确定左右子树 ##

查结点a和结点b的最近公共祖先，简单lca思路：  
1.如果a和b分别在当前根的左右子树，当前的根就是最近祖先  
2.如果根等于a或者根等于b了，根就是最近祖先；判断和a等还是和b等就行了  
3.如果都在左子树上，递归查左子树就可以了。这里找到左子树的边界和根(通过先序中序序列)  
4.如果都在右子树上，递归查右子树。

## 代码1：不建树的做法，参考柳婼blog~ ##

#include<bits/stdc++.h>
    using namespace std;
    
    vector<int> in, pre;
    map<int, int > pos;
    
    //先序遍历第一个遍历到的是根，中序遍历确定左右子树
    
    //lca 递归之美 parms:中序左边界 中序右边界 先序遍历到的根的下标 ab值
    void lca(int inl, int inr, int preRoot, int a, int b) {
        if (inl > inr) return;//出错
        int inRoot = pos[pre[preRoot]], aIn = pos[a], bIn = pos[b];//取当前根、左边、右边、位置
        if (aIn < inRoot && bIn < inRoot) lca(inl, inRoot - 1, preRoot + 1, a, b);//如果a和b都在左子树，递归查找左子树。参数变化(参考中序遍历):左子树边界(inl~inRoot),先序遍历到下一个结点也就是preRoot+1
        else if (aIn > inRoot && bIn > inRoot) lca(inRoot + 1, inr, preRoot + 1 + (inRoot - inl), a, b);//如果ab都在右子树,递归查找右子树。参数变化:找到中序右子树的界限preRoot+1~inr,找到右子树的先序遍历的根(当前的preRoot + (中序根-左边界inl) + 1)，因为右子树先序遍历总是在最后的，等所有左子树上的结点遍历完了才开始遍历右子树，左子树上结点个数也就是需要加的偏移量
        else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot)) printf("LCA of %d and %d is %d.\n", a, b, in[inRoot]);//如果ab一左一右,那么根节点就是他们的最近公共祖先
        else if (aIn == inRoot) 
            printf("%d is an ancestor of %d.\n", a, b);//如果a是根,a就是b的祖先
        else if (bIn == inRoot)
            printf("%d is an ancestor of %d.\n", b, a);//同上
    }
    
    
    int main() {
        int m, n, a, b;
        cin >> m >> n;
        in.resize(n + 1), pre.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> in[i];
            pos[in[i]] = i;//存储中序结点所在位置下标
        }
        for (int i = 1; i <= n; i++) cin >> pre[i];
        for (int i = 0; i < m; i++) {
            cin >> a >> b;
            if (pos[a] == 0 && pos[b] == 0) {
                printf("ERROR: %d and %d are not found.\n", a, b);
            }
            else if (pos[a] == 0 || pos[b] == 0) {
                printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);
            }
            else {
                lca(1, n, 1, a, b);
            }
        }
        return 0;
    }

## 代码2：递归建树，查lca ##

链表树，lca也不用优化的  
查结点a和结点b的最近公共祖先，简单lca思路：  
1.如果a和b分别在当前根的左右子树，当前的根就是最近祖先  
2.如果根等于a或者根等于b了，根就是最近祖先；判断和a等还是和b等就行了  
3.上述条件都不满足的话，就递归查左子树，递归查右子树。  
[点击查看][Link 1]

## 另：PAT常考树的前中后遍历问题 ##

后序确定根节点，中序找到根节点的下标后，根节点左边就是左子树、右边就是右子树了。

1.[已知后序与中序输出前序---不建树做法 ][---_]

2.PAT 甲级1020 [已知后序与中序输出层序---不建树做法(重点在于理清楚左右子树的root、left、right下标) ][---_root_left_right_]

与上面方法相比下面方法，把当前遍历到的根节点设置为全局变量cur，先遍历右子树、再遍历左子树；  
符合后序遍历的遍历步骤（左右根），不需要计算左子树根的下标，所以更简单直观

3.PAT 甲级1020 [已知后序与中序输出层序---建树做法 (递归建树的 left和right下标更直观)][---_ _ left_right]

4.PAT 甲级1119 [已知后序与先序输出中序---搞清楚下标 ][---_ 1]

getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);  
getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);  
前序的开始的第一个应该是后序的最后一个是相等的，这个结点就是根结点。  
以后序的根结点的前面一个结点作为参考，寻找这个结点在前序的位置，就可以根据这个位置来划分左右孩子，递归处理。

重点在于后序的下标确定方法：  
左子树区间也就等于：\[posleft，posleft + 左子树结点的个数 - 1\]  
左子树结点个数 就等于 （前序中当前根节点索引的位置 - 左子树前序左边界preleft）

综上 左子树区间就是\[posleft，posleft+（前序中当前根节点索引的位置 - 左子树前序左边界preleft） \]，  
右子树亦同，右子树区间\[posleft + 左子树结点的个数 ，postRight - 1\]

小结：几道题都需计算清楚 在后序遍历中”根的下标位置“。

转载于:https://www.cnblogs.com/fisherss/p/11139503.html

[Link 1]: https://blog.csdn.net/qq_41317652/article/details/82557975
[---_]: https://www.liuchuo.net/archives/2090
[---_root_left_right_]: https://www.liuchuo.net/archives/2100
[---_ _ left_right]: https://blog.csdn.net/xyt8023y/article/details/46273967
[---_ 1]: https://blog.csdn.net/liuchuo/article/details/52505179