PAT甲级树类题目——笔记与模板（21.1.26）

此为个人练习PAT题目中的笔记，争取让PAT中该类问题都能够以尽可能相同的模板进行套用，或是能够以较为容易理解的方式来解决。同时这也是个人第一次使用markdown语句写的笔记，必然存在很多不足，如果有任何建议还请不吝指教（捂脸）。

多叉树

这类问题与图的知识较为紧密（毕竟本质上树是特殊的图），通常可以采用算法基础课中的模板来解决，因此首先来回忆一下y总给出的树与图邻接表模板。

1539. 等重路径，1565. 供应链总销售额，1580. 供应链最高价格，1596. 供应链最低价格

存储结构

// 初始化
idx = 0;
memset(h, -1, sizeof h);

// 对于每个点k，开一个单链表，存储k所有可以走到的点
// h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

遍历方式

//深度优先遍历
int dfs(int u){
    st[u] = true; // st[u] 表示点u已经被遍历过
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

//宽度优先遍历
void bfs(){
    queue<int> q;
    st[1] = true; // 表示1号点已经被遍历过
    q.push(1);

    while (q.size()){
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (!st[j]){
                st[j] = true; // 表示点j已经被遍历过
                q.push(j);
            }
        }
    }
}

熟练运用上述模板可以解决部分多叉树树的问题，但PAT中还会遇到很多二叉树类的问题，此时该模板便力不从心了。为了更好的解决这类问题，我们需要针对二叉树设计更加方便的模板。

基本二叉树

比较常见的是用结构体+指针（或数组）的方式来定义，这种方法较为直观，容易理解，但个人感觉写起来比较麻烦。因此尝试以类似y总给出的数组模板方式来写二叉树。

基本二叉树1——输入权值建立二叉搜索树

1605. 二叉搜索树最后两层结点数量 ，1552. AVL树的根，1616. 判断完全 AVL 树，

树的存储

//root为根结点坐标，初始值设为-1以方便进行建树
// l[i]=j,r[i]=j分别表示编号为i的结点的左、右儿子编号为j
// e[i]存储编号为i的结点的权值，对于只需存储结点编号的树类题目则可完全忽略
int root=-1;
int l[N], r[N], e[N], idx;

// 初始化
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);

建树方法

// u为结点编号，w为本次插入结点的权值
void insert(int &u,int w){
    if(u==-1){
        //根据结点编号来决定，此为从1开始编号；从0开始只需变为idx++
        u=++idx，e[u]=w;
    }
    else if(w<=e[u]) insert(l[u],w);
    else insert(r[u],w);
}

// 每次输入一个值便执行insert来插入
insert(root,w);

基本二叉树2——已知前/后序遍历+中序遍历建树

标准模板题
1497. 树的遍历，1631. 后序遍历，1620. Z 字形遍历二叉树
模板变题
1527. 判断二叉搜索树 ，1576. 再次树遍历 ，1628. 判断红黑树

模板变题.Pro

1609. 前序和后序遍历

树的存储

此方法通过unordered_map来存储树。

// in_pos[i]=j意为权值为i的点在中序序列的位置为j
// l[i]=j,r[i]=j表示权值为i的左、右子树权值为j
// pre[N],in[N],post[N]分别存储前序、中序、后序序列
unordered_map<int,int> in_pos,l,r;
int pre[N],in[N],post[N];

// 中序序列的读取
for(int i=0;i<n;i++){
        cin>>in[i];
        in_pos[in[i]]=i;
}

建树方法

//后序+中序建树
int build(int il,int ir,int pl,int pr){
    int root=post[pr];
    int k=in_pos[root];
    if(k>il) l[root]=build(il,k-1,pl,pl+k-il-1);
    if(k<ir) r[root]=build(k+1,ir,pl+k-il,pr-1);
    return root;
}

遍历方法

// BFS
void bfs(int root){
    queue<int> q;
    q.push(root);

    while(q.size()){
        int t=q.front();
        q.pop();
        cout<<(t==root?"":" ")<<t;
        if(l.count(t)) q.push(l[t]);
        if(r.count(t)) q.push(r[t]);
    }
}

其他知识点

AVL树（自平衡二叉搜索树）

AVL树的存储与建树方法可参考 基本二叉树1

1552. AVL树的根，1616. 判断完全 AVL 树

树的存储

// 存储结构
int l[N],r[N],e[N],idx;
int h[N];// 存储点的高度

建树方法

// 更新高度
void update(int u){
    int hl=0,hr=0;
    if(l[u]!=-1) hl=h[l[u]];
    if(r[u]!=-1) hr=h[r[u]];
    h[u]=max(hl,hr)+1;
}

// 右旋
void R(int &u){
    int p=l[u];
    l[u]=r[p],r[p]=u;
    update(u),update(p);
    u=p;
}

// 左旋
void L(int &u){
    int p=r[u];
    r[u]=l[p],l[p]=u;
    update(u),update(p);
    u=p;
}

// 计算子树高度差
int get_balance(int u){
    int hl=0,hr=0;
    if(l[u]!=-1) hl=h[l[u]];
    if(r[u]!=-1) hr=h[r[u]];
    return hl-hr;
}

//插入结点建树
void insert(int &u,int w){
    if(u==-1){
        u=idx++,e[u]=w;
    }
    else if(w<e[u]){
        insert(l[u],w);
        if(get_balance(u)==2){
            if(get_balance(l[u])==1) R(u);
            else L(l[u]),R(u);
        }
    }
    else if(w>=e[u]){
        insert(r[u],w);
        if(get_balance(u)==-2){
            if(get_balance(r[u])==-1) L(u);
            else R(r[u]),L(u);
        }
    }
    update(u);
}

完全二叉树

1550. 完全二叉搜索树，1600. 完全二叉树，1616. 判断完全 AVL 树，1649. 堆路径

完全二叉树都可以采用一个一维数组来存储，并且若结点编号为$1\sim N$，那么对于编号为$k$的结点，其左、右子结点编号分别为$2k$、$2k+1$（子结点存在条件$2k \le N$，$2k+1 \le N$）。

二叉搜索树

二叉搜索树的基本性质

1. 若任意结点的左子树非空，那么左子树上的所有结点的值均小于（或等于）其根结点的值；
2. 若任意结点的右子树非空，那么右子树上的所有结点的值均大于（或等于）其根结点的值；
3. 任意结点的左、右子树也分别为二叉搜索树。

注意：与根节点数据相同的点是插入左子树还是右子树要根据具体题目要求来定。

二叉搜索树的建立

二叉搜索树的一个重要性质：其中序遍历正好是所有结点从小到大输出。由此可以在得到其前序/后序遍历的情况下通过排序得到二叉搜索树的中序遍历，进行建树。

若是不断输入权值来建树，则应参考方法1来建树。

最近公共祖先问题

对于公共祖先问题，可以有以下结论

1. 如果p结点是q结点的祖先，那么p结点和q结点的最近公共祖先为p结点。
2. 如果q结点是p结点的祖先，那么p结点和q结点的最近公共祖先为p结点。
3. 否则，设p结点和q结点的最近公共祖先为t结点，那么：
   a) p结点和q结点必定分居在t结点的不同子树中；
   b) 整颗二叉树必定只有t结点满足上一个性质；

普通二叉树的LCA

1644. 二叉树中的最低公共祖先

结合上述结论，对于给出前/后序遍历+中序遍历的普通二叉树，我们可以参考基本二叉树2的方法不断递归找出公共祖先。

下面模板的思路为

1. 如果k==up或vp，即根结点的位置与u或v其中之一相同，便返回根结点；

2. 如果(k-up)*(k-vp)<0，即u和v分别分居根结点的左、右子树，此时根结点就是最近公共祖先，返回根结点；

3. 若up<k且vp<k，即u和v都在左子树，向左子树进行递归遍历；

4. 若up>k且vp>k，即u和v都在右子树，向右子树进行递归遍历。

其中1.2.条件可以合并为(k-up)*(k-vp)<=0。

int u,v;// 查询公共祖先的两个结点
int in[N],pre[N];
unordered_map<int,int> in_pos;// 存储中序序列的位置

// 递归找出最近公共祖先
int LCA(int il,int ir,int pl,int pr){
    int k=in_pos[pre[pl]],up=in_pos[u],vp=in_pos[v];

    if((k-up)*(k-vp)<=0) return pre[pl];
    else if(k>up) return LCA(il,k-1,pl+1,pl+k-il);// u、v都在左子树,向左子树进行递归
    else return LCA(k+1,ir,pl+k-il+1,pr);// u、v都在右子树，向右子树进行递归
}

// 中序序列的读取
for(int i=0;i<n;i++){
        cin>>in[i];
        in_pos[in[i]]=i;
}

二叉搜索树的LCA

1636. 最低公共祖先

因为二叉搜索树排序后得到的序列便是中序序列，所以一种方法是通过将读入的前/后序遍历排序得到中序序列后，直接套用上面的模板来解题。