題目描述

現給出一棵N個結點二叉樹，問這棵二叉樹中最長鏈的長度為多少，保證了1號結點為二叉樹的根。

輸入

第1行為包含了一個正整數N，為這棵二叉樹的結點數，結點標號由1至N。
接下來N行，這N行中的第i行包含兩個正整數l[i], r[i]，表示了結點i的左兒子與右兒子編號。如果l[i]為0，表示結點i沒有左兒子，同樣地，如果r[i]為0則表示沒有右兒子。

輸出

包括1個正整數，為這棵二叉樹的最長鏈長度。

樣例輸入

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

樣例輸出

4

提示

樣例解釋
4-2-1-3-6為這棵二叉樹中的一條最長鏈。

對于100%的數據，有N≤100000，且保證了樹的深度不超過32768。

思路分析

使用深度優先搜索(DFS)計算每個節點的深度，然后遍歷所有節點，計算通過每個節點的最長鏈（左右子樹深度之和），取最大值作為結果。

二叉樹的深度是指從根節點到葉子結點時，最多經過了幾層。

在如上圖所示的二叉樹中，我們令：

節點5、6、7的深度為1；

節點3、4的深度為2；

節點2的深度是3；

節點1的深度是4。

采用深度優先搜索計算每個節點u的深度depth[u]。初始化depth數組N個元素的值為0。如果u=0，說明該節點不存在，直接返回。深搜節點u的左子節點和右子節點，節點u的深度為其左右子節點深度的最大值加一。

void dfs(int u){if(u==0)return;dfs(left_child[u]);dfs(right_child[u]);depth[u]=max(depth[left_child[u]],depth[right_child[u]])+1;
}

遍歷n個節點（1-based indexing），計算通過該節點的最長鏈（即左子樹深度+右子樹深度），并更新最大值。

for(int i=1;i<=n;i++){int len=0;if(left_child[i]){len+=depth[left_child[i]];}if(right_child[i]){len+=depth[right_child[i]];}ans=max(ans,len);
}

代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,l,r,ans;
vector<int>left_child(N+1);
vector<int>right_child(N+1);
vector<int>depth(N+1,0);
void dfs(int u){if(u==0)return;dfs(left_child[u]);dfs(right_child[u]);depth[u]=max(depth[left_child[u]],depth[right_child[u]])+1;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>l>>r;left_child[i]=l;right_child[i]=r;}dfs(1);for(int i=1;i<=n;i++){int len=0;if(left_child[i]){len+=depth[left_child[i]];}if(right_child[i]){len+=depth[right_child[i]];}ans=max(ans,len);}cout<<ans;return 0;
}