简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; const int MAXN = 2e5 + 7; struct node {   int left, right; } t[MAXN]; int n; void build() {   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; t[i].left &gt;&gt; t[i].right;   } } #define rep1(i, n) for (int i = 1; i &lt;= 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 &gt;&gt; n;   build();   cout &lt;&lt; dfs(1);   return 0; }</pre><pre class="brush:cpp;toolbar:false">//题解2 #include &lt;algorithm&gt; #include &lt;iostream&gt; 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 &amp;&amp; meng[root][1] == -1)     return 1;   else {     int left = 0, right = 0;     if (meng[root][0] &gt;= 0)       left = dfs(meng[root][0]);     /*如果该节点满足不为-1证明它有父节点,     递归回去去证明它的父节点上面是否也有父节点*/     if (meng[root][1] &gt;= 0) {       right = dfs(meng[root][1]);     }     return max(right, left) + 1;   } } int main() {   int n;   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; a &gt;&gt; b;     // 二维是为了更好的判断左孩子还是右孩子,父节点     meng[i][0] = a; // i的左孩子是a     meng[i][1] = b; // i的右孩子是b   }   cout &lt;&lt; dfs(1) &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。