[数据结构与算法]P4913 二叉树深度

题目描述

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

最多有?10^6个结点。

输入格式

无

输出格式

无

输入#1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 输出#1

7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4

2 7

3 6

4 5

0 0

0 0

0 0

0 0

题目解析

本题主要分两步：

1.二叉树的存储问题。本人使用的结构体数组存储，同时本文的左右子树的位置已经给出。

2.二叉树的遍历。遍历问题也是根据左右子树的位置来遍历的。

代码如下：

#include<iostream>
using namespace std;
const int N=1e6;
int sum=0;
struct data
{
	int left,right;
};
struct data tree[N+1];
void dfs(int num,int cnt)
{
	if(tree[num].left==0&&tree[num].right==0)//当左右子树都为0的时候，到了根节点 
	{
		if(cnt>sum) sum=cnt;
		return ;
	}
	dfs(tree[num].left,cnt+1);//访问左子树 
	dfs(tree[num].right,cnt+1);//访问右子树 
} 
int main()
{
	int n,i=1;cin>>n;
	if(n<=1)//当只有根节点的时候直接输出根节点。 
	{
		cout<<n;
		return 0;
	}
	while(n--)//存放左右子树的位置 
	{
		int left,right;cin>>left>>right;
		tree[i].left=left;
		tree[i].right=right;	
		i++;
	}
	dfs(1,1);//因为前面已将至多有一个根节点的情况提前判断了，所以这里默认有根节点 
	cout<<sum;
	return 0;
}