二叉树刷题总结

最近在刷PAT甲级，发现在PAT考试中涉及的两种难度较高的大题，基本都是二叉树和图论的范畴，由此可见树论这块的重要性。在今年蓝桥杯比赛中，也由于平时疏忽了二叉树这块的学习，所以当时有一个15分的二叉树大题，虽然难度不高，但是我却没有写出来，所以就先来总结一下二叉树的有关内容吧。

其实我认为二叉树的应用其实就是DFS的应用，所以要熟练掌握DFS算法，才能够更好地理解二叉树的题目。

对于二叉树的存储，我一般是采用结构体进行存储比较方便, 例如：

struct node {
    int left, right;
} tree[100005];  

如果涉及的题目不是二叉树，而是树的话，那我们可以采用：

struct node {
    double data;
    vector<int> child;
} tree[100005];

先从一道简单的题目开始：

1.二叉树深度

题目链接： 洛谷 P4913

题目描述：

给出每个节点的两个儿子节点，建立一棵二叉树（根节点为 1），如果是叶子节点，则输入0 0。建好树后希望知道这棵二叉树的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

最多有 10^6 个结点。

题解：涉及到树的深度，我们首先想到DFS进行深搜，题目已经给定了根节点，所以在DFS的过程中，遇到叶子节点的话，不断的更新深度的最大值。

#include <iostream>
using namespace std;
struct node {
    int left, right;
}tree[100005];  
int n, res;
void dfs(int root, int len) {
    if(root == 0) {   // 判断是否为叶子节点
        res = max(res, len - 1);
        return;
    }
    dfs(tree[root].left, len + 1);
    dfs(tree[root].right, len + 1);
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> tree[i].left >> tree[i].right; 
    }
    dfs(1, 1);
    cout << res << endl;
    return 0;
}

接下来，我们可以看一道复杂一些的二叉树的应用题

2.Infix Expression

题目链接：Infix Expression

题解：这个题我们需要根据每个节点的字符、左右节点的值，来求出二叉树代表的表达式。其实观察输出样例，我们发现它的结果就是二叉树的先序遍历，不过我们需要特殊处理（）字符。这个题目，我们首先需要根据输入数据得到对应的根节点，然后进行DFS搜索，通过判断是否为根节点，来考虑是否添加括号。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define ll long long
struct node {
    string val;
    int left, right;
}v[25];
int vis[25];
int root;
string dfs(int idx) {
    if(idx == -1) return "";
    // 根据实际情况，我们发现只要右节点不为0的话，那么就可以继续遍历，例如题目中的-d
    if(v[idx].right != -1) {
        v[idx].val = dfs(v[idx].left) + v[idx].val + dfs(v[idx].right);
        // 如果非叶子节点不是根节点，那么需要加括号
        if(idx != root) {
            v[idx].val = '(' + v[idx].val + ')';
        }
    }
    return v[idx].val;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> v[i].val >> v[i].left >> v[i].right;
        if(v[i].left != -1)  vis[v[i].left] = 1;
        if(v[i].right != -1) vis[v[i].right] = 1;
    }
    // 找出根节点
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            root = i;
            break;
        }
    }
    cout << root << endl;
    cout << dfs(root) << endl;
    return 0;
}

3.Tree Traversals Again

题目链接：Tree Traversals Again

题解：栈实现的是二叉树的中序遍历（左根右），而每次push入值的顺序是二叉树的前序遍历（根左右），所以该题可以用二叉树前序和中序转后序的方法做。root为当前子树的根结点在前序pre中的下标，start和end为当前子树的最左边和最右边的结点在中序in中的下标。用i找到当前子树的根结点root在中序中的下标，然后左边和右边就分别为当前根结点root的左子树和右子树。用递归就可以实现。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
#define ll long long
const int MAXN = 35;
int n, m, cnt, root;
// 分别代表二叉树的前序，中序和后序遍历
vector<int> pre, in, post;
stack<int> s;

// root代表前序遍历对应的根节点索引，start，end代表中序遍历该根节点下的元素索引
void postorder(int root, int start, int end) {
    // 剪枝
    if(start > end) {
        return;
    }
    int i = start;
    // 找到中序遍历对应的根节点的位置
    while(i < end && in[i] != pre[root]) i++;
    // 左边的根节点是中心根节点索引值+1
    postorder(root + 1, start, i - 1);
    // 右边的根节点是中心根节点索引值+左边元素的个数i - start + 1
    postorder(root + i - start + 1, i + 1, end);
    // 后序遍历的顺序，先左，在右，最后根节点加入
    post.push_back(pre[root]);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= 2 * n; i++) {
        char str[5];
        scanf("%s", str);
        if(strlen(str) == 4) {
            int num;
            scanf("%d", &num);
            // 入栈的顺序是二叉树前序遍历的过程
            pre.push_back(num);
            s.push(num);
        } else {
            // 出栈的顺序是二叉树中序遍历的过程
            in.push_back(s.top());
            s.pop();
        }
    }
    // 递归遍历
    postorder(0, 0, n - 1);
    printf("%d", post[0]);
    for(int i = 1; i < n; i++) {
        printf(" %d", post[i]);
    }
    return 0;
}

4.Invert a Binary Tree

题目链接：Invert a Binary Tree

题解：这个题给定了每个点的左右节点的值，然后求得其翻转二叉树的中序遍历和层序遍历，其实本质是一样的，翻转以后，我们中序遍历的顺序变成了右—中—左，层序遍历在每层的遍历顺序改为从右到左，所以我们在结构体的里面，添加了level和idx，代表了节点所在的层数和索引。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define ll long long
const int MAXN = 105;
int isroot[MAXN];
int n, root;
// l,r代表左右节点，level代表层数，idx代表索引值
struct node
{
    int id, l, r, level, idx;
} tree[MAXN];
// in,ceng代表中序，层序遍历
vector<node> in, ceng;

// 层序遍历，需要按照层数和索引值进行排序，需要cmp进行自定义排序
bool cmp(node a, node b)
{
    if (a.level != b.level)
        return a.level < b.level;
    return a.idx > b.idx;
}
// root是DFS对应的根节点，level，idx为层数和索引值
void dfs(int root, int level, int idx)
{
    if (tree[root].r != -1)
    {
        // 右边进行遍历，由于idx初始值为0，所以右孩子是idx * 2 + 2
        dfs(tree[root].r, idx * 2 + 2, level + 1);
    }
    // 根节点进入数组
    in.push_back({root, 0, 0, idx, level});
    if (tree[root].l != -1)
    {
        // 左边进行遍历，由于idx初始值为0，所以右孩子是idx * 2 + 1
        dfs(tree[root].l, idx * 2 + 1, level + 1);
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string lchild, rchild;
        cin >> lchild >> rchild;
        if (lchild == "-")
        {
            tree[i].l = -1;
        }
        else
        {
            // stoi函数，讲string转换为int
            tree[i].l = stoi(lchild);
            isroot[stoi(lchild)] = 1;
        }
        if (rchild == "-")
        {
            tree[i].r = -1;
        }
        else
        {
            tree[i].r = stoi(rchild);
            isroot[stoi(rchild)] = 1;
        }
    }
    // root是根节点
    for (int i = 0; i < n; i++)
    {
        if (!isroot[i])
        {
            root = i;
            break;
        }
    }
    dfs(root, 0, 0);
    ceng = in;
    // 自定义排序
    sort(ceng.begin(), ceng.end(), cmp);
    cout << ceng[0].id;
    for (int i = 1; i < ceng.size(); i++)
    {
        cout << " " << ceng[i].id;
    }
    cout << endl;
    cout << in[0].id;
    for (int i = 1; i < in.size(); i++)
    {
        cout << " " << in[i].id;
    }
    return 0;
}

今日份的总结就先到这里了啊，多多支持我的博客！