A40950. 二叉树的深度
填空题
困难
知识点
题目描述
二叉树的深度
题目描述
给定一棵二叉树，求该二叉树的深度
二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度
输入
第一行是一个整数n，表示二叉树的结点个数。二叉树结点编号从1到n，根结点为1，n <= 10 接下来有n行，依次对应二叉树的n个节点。 每行有两个整数，分别表示该节点的左儿子和右儿子的节点编号。如果第一个（第二个）数为-1则表示没有左（右）儿子
输出
输出一个整型数，表示树的深度
样例输入
3
2 3
-1 -1
-1 -1
样例输出
2
参考答案
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int node_id;
TreeNode* left;
TreeNode* right;
};
class Solution {
private:
TreeNode* treelist;
int max_depth = 0;
int traverse(TreeNode* root) {
if(root == NULL){
return 0;
}
int left = traverse(root->left);//左子节点最大深度
int right = traverse(root->right);//右子节点最大深度
int max_lr = max(left, right) + 1; //包含自身节点所以+1
max_depth = max(max_depth, max_lr);
return max_lr;
}
public:
void buildTree(){
int N;
scanf("%d", &N);
treelist = new TreeNode[N + 1];
memset(treelist, 0, sizeof(treelist));
for(int i = 1; i <= N; i++){
int node_left, node_right;
scanf("%d%d", &node_left, &node_right);
treelist[i].node_id = i;
treelist[i].left = NULL;
if(node_left > 0){
treelist[i].left = &treelist[node_left];
}
treelist[i].right = NULL;
if(node_right > 0){
treelist[i].right = &treelist[node_right];
}
//printf("%d,%d,%d\n", i, treelist[i].left, treelist[i].right);
}
}
int maxDepth() {
TreeNode* root = &treelist[1];
traverse(root);
return max_depth;
}
};
int main() {
#ifdef LOCAL
freopen("t1.in", "r", stdin);
#endif
Solution s;
s.buildTree();//创建二叉树
int max_depth = s.maxDepth();//递归遍历获取二叉树最大深度
printf("%d", max_depth);
return 0;
}
上一题
下一题