简答题
偏难
#7240
二叉树的深度 给定一棵二叉树,求该二叉树的深度 二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度 时…
二叉树的深度
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
struct node {
int left, right;
} t[MAXN];
int n;
void build() {
for (int i = 1; i <= n; i++) {
cin >> t[i].left >> t[i].right;
}
}
#define rep1(i, n) for (int i = 1; i <= n; i++)
inline int dfs(int x) {
if (x == -1)
return 0;
return max(dfs(t[x].left), dfs(t[x].right)) + 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
build();
cout << dfs(1);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}</pre>
这道题暂未补解析。