/ Vijos / 题库 /

二叉树的子树

二叉树的子树

时间限制:1秒  内存限制:256M


【题目描述】

  给出一棵含 \(N\) 个结点的二叉树,结点编号为 \(1..N\),请你编程计算:
  1、以 \(x\) 为根的子树的结点数目
  2、树中叶子结点数:

【输入格式】

  第 1 行一个整数 \(N\),表示树的结点数量;
  接下来的 \(N\) 行,每行两个整数 \(a,b\),第 \(i+1\) 行的整数表示结点 \(i\) 的左孩子和右孩子的编号,如果 \(a=0\),则表示结点 \(i\) 没有左孩子 ,如果 \(b=0\),则表示结点 \(i\) 没有右孩子。
  最后一行一个整数\(x(1≤x≤N)\)。

【输出格式】

  第 1 行:一个整数表示给出以 \(x\) 为根的子树的结点数量;;
  第 2 行:一个整数,表示叶结点的数目;

【输入输出样例】

 Input

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

 Output

4
3

【数据限制】

  对于 \(100\%\) 的数据 \(1≤N≤50000\)。

【来源】

  Mr.he

信息

ID
2430
难度
9
分类
树结构 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
4
上传者