P4913【深基16.例3】二叉樹(shù)深度-創(chuàng)新互聯(lián)

題目描述

有一個(gè)?n(n \le 10^6)n(n≤106)?個(gè)結(jié)點(diǎn)的二叉樹(shù)。給出每個(gè)結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)編號(hào)（均不超過(guò)?nn），建立一棵二叉樹(shù)（根節(jié)點(diǎn)的編號(hào)為?11），如果是葉子結(jié)點(diǎn)，則輸入?0 0。

10多年的丁青網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷(xiāo)推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整丁青建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)公司從事“丁青網(wǎng)站設(shè)計(jì)”,“丁青網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

建好這棵二叉樹(shù)之后，請(qǐng)求出它的深度。二叉樹(shù)的深度是指從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)時(shí)，最多經(jīng)過(guò)了幾層。

輸入格式

第一行一個(gè)整數(shù)?nn，表示結(jié)點(diǎn)數(shù)。

之后?nn?行，第?ii?行兩個(gè)整數(shù)?ll、rr，分別表示結(jié)點(diǎn)?ii?的左右子結(jié)點(diǎn)編號(hào)。若?l=0l=0?則表示無(wú)左子結(jié)點(diǎn)，r=0r=0?同理。

輸出格式

一個(gè)整數(shù)，表示大結(jié)點(diǎn)深度。

輸入輸出樣例

輸入 #1復(fù)制

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

輸出 #1復(fù)制

4

1.這道題，去創(chuàng)建二叉樹(shù)去做的話，是比較麻煩的，用dfs可以。

2.這道題之所以用dfs，是因?yàn)樗斎氲臄?shù)據(jù)適合使用dfs，這個(gè)題目的意思一定要搞明白，之前就是搞不明白，然后大眼瞪小眼看了一下午沒(méi)明白。

這道題說(shuō)的是??第?i行兩個(gè)整數(shù)?l、r，分別表示結(jié)點(diǎn)?i的左右子結(jié)點(diǎn)編號(hào)。

以下面這道題目為列子：

創(chuàng)建出來(lái)的二叉樹(shù)：

這里是不計(jì)算 0 的節(jié)點(diǎn)的。所以是很適合使用dfs的。

我們可以先把節(jié)點(diǎn)記下來(lái)，在一個(gè)結(jié)構(gòu)體中。

然后使用 dfs的方式去使用就可以，因?yàn)閐fs的特點(diǎn)是不撞南墻不回頭，當(dāng)它遇到0時(shí)，我們結(jié)束即可。從根節(jié)點(diǎn)開(kāi)始遞歸，分別遞歸左右子樹(shù)，即可。

代碼如下：（C語(yǔ)言）

#include#define N 1000010
struct node
{
	int l;
	int r;
}a[N];
int max;
int dfs(int x,int step)
{
	if(x==0)
	{
		if(max

c++代碼：

#include#includeusing namespace std;

const int N = 1e6 + 10;
struct node 
{
	int l;
	int r;
} a[N];
int maxstep;
int dfs(int x, int step) 
{
	if (x == 0) 
	{
		if (maxstep< step) maxstep = step;
		return 0;
	}
	dfs(a[x].l, step + 1);
	dfs(a[x].r, step + 1);
}

int main() 
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i<= n; i++) 
	{
		cin >>a[i].l >>a[i].r;
	}
	dfs(1, 0);
	cout<< maxstep<< endl;
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧