p4913 【深基16.例3】二叉树深度

### 回答1：
题目描述：

给定一棵二叉树，求其深度。

输入格式：

第一行包含一个整数 n，表示二叉树的节点个数。

接下来 n 行，每行包含三个整数 fa, lch, rch，表示节点的父节点编号，左儿子编号和右儿子编号。根节点的父节点编号为 0，如果某个节点不存在左儿子或右儿子，则对应的编号为 −1。

输出格式：

输出一个整数，表示二叉树的深度。

数据范围：

1≤n≤1000

输入样例：

5
0 1 2
1 3 -1
2 -1 4
3 -1 -1
4 -1 -1

输出样例：

3

解题思路：

递归求解二叉树深度，每次递归时，将左右子树的深度取最大值加一即可。

C++ 代码

### 回答2：
题目：p4913 【深基16.例3】二叉树深度。

【题目描述】
给定一棵二叉树，求其深度。
【输入格式】
第一行包含一个整数n，表示二叉树的节点个数。
接下来n行，每行包含三个整数，表示一个节点及其左右子节点的编号，其中-1表示该节点为空。
【输出格式】
输出一个整数，表示二叉树的深度。

【示例输入】
6
1 2 3
2 4 5
3 -1 6
4 -1 -1
5 -1 -1
6 -1 -1

【示例输出】
3

【解题思路】
采取递归的方式求解二叉树的深度。对于一个二叉树来说，它的深度等于其左子树深度和右子树深度的较大值加1。
【代码实现】

def tree_depth(root, depth):
    if root == -1:  # 如果节点为空，返回深度
        return depth
    else:
        left_depth = tree_depth(nodes[root][0], depth + 1)  # 左子树深度
        right_depth = tree_depth(nodes[root][1], depth + 1)  # 右子树深度
        return max(left_depth, right_depth)  # 返回左右子树深度的较大值

n = int(input())  # 节点个数
nodes = {}  # 节点字典
for i in range(n):
    nodes[i + 1] = list(map(int, input().split()))

depth = tree_depth(1, 0)  # 从根节点开始求解深度，初始化深度为0
print(depth)

【代码说明】
首先定义一个递归函数tree_depth，传入两个参数：root表示当前节点的编号，depth表示当前节点的深度。
如果当前节点为空，即root为-1，表示到达叶子节点，返回深度depth。
如果当前节点不为空，分别求解左子树和右子树的深度，即left_depth和right_depth。
最后返回左右子树深度的较大值，即max(left_depth, right_depth)。
读入节点个数n，并创建一个字典nodes，用于存储节点及其左右子节点的编号。
接下来，使用循环读入每个节点的信息，并将其存入字典nodes中。
最后调用tree_depth函数，从根节点开始求解深度，初始深度为0，将结果打印出来。