[PAT]甲级题库刷题记录贴

Posted on |
Words count in article: 1.8k | Reading time ≈ 7

2019.5.12

柳神推荐的甲级题库刷题方法：PAT甲级共155道题目

##”树的遍历”

###题目集合

1151、1147、1138、1127、1119、1115、1106、1102、1094、1090、1086、1079、1076、1053、1020、1004

踩坑记录

A1020Tree Traversals

1.判断左右子树是否为空，不能用”!root->lchild”，只能用”root->lchild != NULL”

2.层序遍历中最后不要空格，通过”计数”来实现格式控制

####A1053Path of Equal Weight

1.主要是DFS函数的编写，依据“sum与S”的三种关系进行处理，在”sum==S”的情况中要注意是否遍历到叶子结点的判断。

A1151LCA in a Binary Tree

1.已知中序与先序、后序、层序任意一种建树，注意临时的根节点申明为：

1
node* root = new node;

2.已知中序遍历与先序遍历构建树的简便方法

1
2
3
4
5
6
7
8
9
10
11
//其中inl与inr为中序遍历的左端元素和右端元素
//preRoot为先序遍历中root结点在pre[]中的序号
void lca(int inl,int inr,int preRoot,int a,int b)
{}
//输入中序遍历序列的时候记录"输入的序号i"
//引入pos[]数组的这个技巧很巧妙
for(int i=1;i<=n;i++)
    {
        scanf("%d",&in[i]);
        pos[in[i]] = i;//记录原输入顺序
    }

A1147Heaps

1.层序遍历数组[0…n-1]中，父结点序号和左右子结点序号的关系：left=parentX2+1;right=parentX2+2

若为[1…n]中，父结点序号和左右子结点序号的关系：left=parentX2;right=parentX2+1

2.不用构建树的话，直接pre.resize(n),不用pre.resize(n+1);

3.后序遍历的递归写法-注意格式的控制技巧

root==0的时候说明输出到最后一个数，则换行；否则只输出空格

A1138Postorder Traversal

1.由遍历序列建树，找出根节点在中序遍历中的位置

1
for(int i=inL;i<=inR;i++){}

2.已知前序和中序，求后序-熟悉简单写法，抛弃算法笔记的复杂写法

1
2
3
4
5
6
7
8
9
10
11
//参数只需要prel,inl,inr
void postOrder(int prel,int inl,int inr)
{
    //递归边界
    if(inl>inr) return;
    //递归主体
    int i = inl;
    while(in[i]!=pre[prel]) i++;
    postOrder(prel+1,inl,i-1);
    postOrder(prel+i-inl+1,i+1,inr);
}

A1127ZigZagging on a Tree

1.建树-需要记录节点层数的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//结点的结构-不用左右子结点
struct node
{
    int index,depth;
};
//通过二维数组表示法表示一棵树
int tree[35][2]
//建树办法
//多了一个index参数
void dfs(int &index,int inLeft,int inRight,int postLeft,int postRight)
{
    //递归边界
    if(inLeft > inRight) return;
    //递归主体
    index = postRight;
    int i=0;
    while(in[i]!=post[postRight]) i++;
    dfs(tree[index][0],inLeft,i-1,postLeft,postLeft+(i-inLeft)-1); 
    dfs(tree[index][1],i+1,inRight,postLeft+(i-inLeft),postRight-1);
}

A1119Pre- and Post-order Traversals

1.判断树是否唯一的依据——一个结点可能是根的左孩子也可能是根的右孩子——找左子树和右子树的根结点，如果相同，则不唯一，假设为右子树根结点；如果不相同，则唯一，继续递归建树

注意：递归边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if(preLeft==preRight)
    {
        in.push_back(pre[preLeft]);
        return;
    }
    if(pre[preLeft]==post[postRight])
    {
        int i=preLeft+1;
        //在先序遍历中找右子树的根节点
        while(i<=preRight && pre[i]!=post[postRight-1]) i++;
        //可以区分左右子树
        if(i-preLeft>1)
        {
            getIn(preLeft+1,i-1,postLeft,postLeft+(i-preLeft-1)-1);
        }else
        {
            //不唯一
            //右子树根节点和左子树根结点相同，无法判断是左子树还是右子树
            unique = false;
        }
        //当不唯一的时候，假设为右子树根结点
        in.push_back(post[postRight]);
        getIn(i,preRight,postLeft+(i-preLeft-1),postRight-1);
    }

A1115Counting Nodes in a BST

1.递归建树的递归边界先写好”return”，不管有没有其他语句，非常容易忽略

2.BST建树的递归模板-思路：输入一个值，插入一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//递归建树-BST-可作为模板
//参数要记住：根节点指针和插入的值
node* build(node* root,int v)
{
    if(root==NULL)
    {
        root = new node();
        root->data = v;
        root->lchild = root->rchild = NULL;
    }else if(v<=root->data)
    {
        root->lchild = build(root->lchild,v);
    }else//相等值放在右子树
    {
        root->rchild = build(root->rchild,v);
    }
    return root;
}

3.连续定义两个指针变量，*的位置要变化

1
2
3
4
5
struct node
{
    int data;
    node *lchild,*rchild;//同时定义两个，则*号要放在变量名前面
};

4.DFS方法记录一棵树对应层数中的结点数——思路：声明一个二维数组num[]

####A1106Lowest Price in Supply Chain

1.树以邻接表的形式存储

1
2
//结点个数
vector<int> v[100005];

2.根据题目要求的两个限制条件——深度最小、叶子结点——写出判断条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int index,int depth)
{
    //递归边界-不符合深度最小
    if(mindepth < depth){}
    //叶子结点-retailer
    if(v[index].size()==0)
    {
        if(mindepth == depth)
        {
        }else if(mindepth > depth)
        {
        }
    }
    //递归
    for(int i=0;i<v[index].size();i++)
    {
        dfs(v[index][i],depth+1);
    }
}

A1102 Invert a Binary Tree

1.Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

2.翻转二叉树的基本思想：在存储的时候所有左右结点都交换——使用RNL的遍历方式即可反转二叉树

1
2
3
4
5
6
7
void dfs(int root,int index,int level)
{
    //RLN-逆中序遍历-可以反转二叉树
    if(a[root].r!=-1) dfs(a[root].r,index*2+2,level+1);
    v1.push_back({root,0,0,index,level});
    if(a[root].l!=-1) dfs(a[root].l,index*2+1,level+1);
}

3.根结点是所有左右结点中没有出现的那个结点

A1094The Largest Generation

1.找出包含结点最多的那层，并输出层数和该层的结点总数

2.根据输入以邻接表表示树 + BFS统计每层的结点数 + 输出

1
2
3
4
5
6
7
//邻接表表示树v[index][i]
//100个结点
vector<int> v[100];

//统计某结点的层数 以及 某层的结点总数
int level[100];
int book[100];

A1090Highest Price in Supply Chain

1.邻接表存储树 + 最大层数以及最大层数的结点数

2.each number Si is the index of the supplier for the i-th member. Sroot for the root supplier is defined to be −1.——Si是i的父节点，Sroot是根结点

3.关键的dfs代码

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
void dfs(int index,int depth)
{
    //叶子结点-retailer
    if(v[index].size == 0)
    {
        //相等
        if(maxDepth == depth)
        {
            maxNum++;
        }
        //更大
        if(maxDepth < depth)
        {
            maxDepth = depth;
            maxNum = 1;
        }
      	//更小
        return;
    }
    //不是retailer
    for(int i=0;i<v[index].size();i++)
    {
        dfs(v[index][i],depth+1);
    }
}

4.r%在输出的时候要注意”r/100”

A1086Tree Traversals Again

1.栈的形式给出一棵二叉树的建立过程-(1) 栈pop输出的顺序的中序遍历(左根右) (2) 栈push输入的顺序是二叉树的前序遍历(根左右)——实际上是前序+中序->后序

2.题目没有说树中的结点值全部不相同——前中后序存储索引值，value数组中存储具体的值，因为索引值一定是不相同的。

A1079Total Sales of Supply Chain

1.统计所有叶子的层数

A1076Forwards on Weibo

1.待做

A1004Counting Leaves

1.待做