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

同一棵树枝上的蚂蚱

题目描述

设有一个二叉树

我们想要在其中实现一个功能，他的目的是为了判断两个结点是否处于二叉树根节点的同一边(跟节点默认是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;
}