本篇博客用来分享自定义方法实现某些功能，可以用来出题

同一棵树枝上的蚂蚱

题目描述

设有一个二叉树

我们想要在其中实现一个功能，他的目的是为了判断两个结点是否处于二叉树根节点的同一边(跟节点默认是1)

输入格式

输入n，代表n组关系

接下来n + 1行，每一行输入两个数a，b

分别代表上一个结点的左右子结点

接着输入你想要判断的两个结点

输出格式

如果处于同一侧，输出 Yes

否则输出 No

输入输出样例

输入 #1

5						
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
2 3

输出 #1

No

说明/提示

解释：假如第一次输入两个数34，说明了1的左结点是3，右结点是4；第二次输入67代表2的左结点是6，右结点是7，如果输入左右结点都是0 和 0代表是根结点

数据规模与约定

对于 100%100% 的数据，只需要保证1 <= n <= 100，0 < a,b < n

AC模版

#include <bits/stdc++.h>
using namespace std;

struct node{
    int left;int right;int val;
};node t[110];

int n,sum,ans = 999999;

bool check(int rt, int a, int b, int flag) {
    if (rt == 0) {
        if(flag == 2) return true;
        else return false;
    }
    if (rt == a || rt == b) {
        if(check(t[rt].left, a, b, flag + 1) || check(t[rt].right, a, b, flag + 1)) return true;
    }else {
        if(check(t[rt].left, a, b, flag) || check(t[rt].right, a, b, flag)) return true;
    }

    return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i].val >> t[i].left >> t[i].right;
    }

    cout << check(1,1,2,0) << endl;

    return 0;
}

二叉树的深度

题目描述

这里有一个二叉树

我们想要确定二叉树上每一个结点的深度是多少(根节点的深度定义为0)

输入格式

输入n，代表n组关系

同时代表了只有n个结点分别是1，2，3，4，5

接下来n + 1行，每一行输入两个数a，b

分别代表上一个结点的左右子结点

输出格式

打印除了根节点外每一个二叉树的结点的深度

输入输出样例

输入 #1

5						
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

输出 #1

1 1 2 2

AC模版

#include <bits/stdc++.h>
using namespace std;

struct node{
    int left;int right;int val;
};node t[110];

int n,sum,ans = 999999;
int target,dp;

void getDeep(int u,int deep) {
    if(u == target) {
        dp = deep;
        return;
    }
    if(u == 0) return;
    getDeep(t[u].left,deep + 1);
    getDeep(t[u].right,deep + 1);

    return;
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i].val >> t[i].left >> t[i].right;
    }

    for(int i = 2;i <= n;i++) {
        target = i;
        getDeep(1,0);
        cout << dp << endl;
    }

    

    return 0;
}

二叉树距离

题目描述

我们假设有一个二叉树

我们想要确定从二叉树上某一个结点到达另一结点之间最少需要走几步

输入格式

输入n，代表有n条线段

从 2 ~ n 行每一行输入两个数a,b分别代表结点a和b之间有一条线段

第n + 1输入两个数，代表我们想要调查那两个结点之间的最短步数

本题默认1为根结点，计算距离时算上首结点和尾结点

输出格式

打印两点之间距离

输入输出样例

输入 #1

10                                
1 2                            
1 3                            
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6

输出 #1

6

模版

#include <bits/stdc++.h>
using namespace std;

struct node{
    int father;int left;int right;int deep;
};

node f[110];

int n;
int a,b,c,d,pd = 0;
int ans3;
int vis[110] = {0};

void getDis(int st,int ed,int dis) {
    if(st == 0 || vis[st]) return;
    if(st == ed) {pd = 1; ans3 = dis; return;}
    vis[st] = 1;
    if(!pd) {
        getDis(f[st].left,ed,dis + 1);
        getDis(f[st].right,ed,dis + 1);
        getDis(f[st].father,ed,dis + 1);   
    }
}
int main(){
    cin >> n;
    for(int i = 1;i < n;i++) {
        cin >> a >> b;
        if(f[a].left == 0) f[a].left = b;
        else f[a].right = b;
        f[b].father = a;
    }


    cin >> c >> d;

    getDis(c,d,1);
    
    cout << ans1 << "\n" << ans2 << "\n" << ans3 << endl;

    return 0;
}