题意:

输出一个二叉树的最深深度

思路:

只要在递归的时候记录最深的深度就行了

#include<iostream>
using namespace std;
const int N=10e6;
int maxn=0;
struct node
{
 int l,r;//左右子树
}tree[N];//一颗"树"
void pre(int x,int t)//前序遍历
{
 maxn=max(maxn,t);//设置最深的深度
 if(tree[x].l!=0)pre(tree[x].l,t+1);//左子树
 if(tree[x].r!=0)pre(tree[x].r,t+1);//右子树
}
int main()
{
 int n;
 cin>>n;//输入
 for(int i=0;i<n;i++)
 {
  int l,r;
  cin>>l>>r;//输入
  tree[i+1].l=l;//设置左子树
  tree[i+1].r=r;//设置右子树
 }
 pre(1,1);//前序遍历
 cout<<maxn;//输出最深值
 return 0;//完结散花
}

#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int tree[100070][3];
int a=0;
void dfs(int u, int h){
	if(tree[u][1]!=0&&tree[u][2]!=0){
		h++;
		dfs(tree[u][1],h);
		dfs(tree[u][2],h);	
		}
	if(tree[u][1]==0&&tree[u][2]!=0){
	h++;
	dfs(tree[u][2],h);			
}
	if(tree[u][2]==0&&tree[u][1]!=0){
	h++;
	dfs(tree[u][1],h);		
}
    if(tree[u][1]==0&&tree[u][2]==0){
	if(h>a){
		a=h;	
	}

}
}
int main(){
	int n,lc,rc;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>lc>>rc;
		tree[i][1]=lc;
		tree[i][2]=rc;
	}
    dfs(1,1);
    cout<<a;
}

极致压行

#include<cstdio>
#include<algorithm>

using namespace std;

struct node
{
	int left,right;
};

node tree[1000001]={};
int n;

int dfs(int n){return n?max(dfs(tree[n].left),dfs(tree[n].right))+1:0;}

int main()
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;++i)
		scanf("%d %d",&tree[i].left,&tree[i].right);
	
	printf("%d",dfs(1));
	return 0;
}

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

struct bfs_node{
	int n,level;	//n:节点，level:层数
};

struct node{
	int l,r;
}t[1000005];

queue<bfs_node> q;
int ans=0;
void bfs(){	
	while(!q.empty()){
		bfs_node rt=q.front();
//		cout<<rt.n<<' ';
		ans=max(ans,rt.level);	//记录最大层数
		if(t[rt.n].l != 0){		//不是0就入栈
			q.push({t[rt.n].l, rt.level+1});
		}
		if(t[rt.n].r != 0){	    //同上
			q.push({t[rt.n].r, rt.level+1});
		}
		q.pop();
	}
}


int main(){
	int n,a,b;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		t[i].l=a;
		t[i].r=b;
	}
	q.push({1,1});
	bfs();
	cout<<ans;
	return 0;
}

题意

输入第 $i$ 个节点的左子树和右子树，输出最深的层数

PS：根为节点 1

思路

找层数，用深搜

记录左子树的层数和右子树的层数，然后返回当前层数、左子树的层数、右子树的层数中的最大值（叶节点的左子树和右子树的层数为 0）

代码

#include <bits/stdc++.h>
using namespace std;
struct tree{
	int l,r;
}a[1000005];
int dfs(int n,int ceng){
	int l = 0,r = 0;	// 叶节点初始化
	if (a[n].l)	l = dfs(a[n].l,ceng + 1);	// 左子树的层数
	if (a[n].r) r = dfs(a[n].r,ceng + 1);	// 右子树的层数
	return max({ceng,l,r});	// 如果是叶节点，返回当前层数；否则返回更大的子树层数
}
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i].l >> a[i].r;	// 输入 i 的左子树和右子树
	}
	cout << dfs(1,1);	// 根为 1，层数为 1
	return 0;
}