【剑指offer】二叉树深度
二叉树 深度 Offer
2023-09-11 14:20:59 时间
转载请注明出处:http://blog.csdn.net/ns_code/article/details/27249675
- 题目描写叙述:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径。最长路径的长度为树的深度。
- 输入:
第一行输入有n,n表示结点数,结点号从1到n。根结点为1。 n <= 10。
接下来有n行,每行有两个个整型a和b。表示第i个节点的左右孩子孩子。a为左孩子。b为右孩子。当a为-1时。没有左孩子。
当b为-1时,没有右孩子。
- 输出:
输出一个整型。表示树的深度。
- 例子输入:
3
2 3
-1 -1
-1 -1
- 例子输出:
2
这是这次用数组存储二叉树,在九度OJ上AC。
思路非常easy,递归实现,代码例如以下:
#include<stdio.h> #include<stdlib.h> typedef struct BTNode { int data; int rchild; int lchild; }BTNode; int max(int a,int b) { return a>b ? a:b; } /* 求二叉树的深度 */ int TreeDepth(BTNode *pTree,int index) { if(pTree == NULL) return 0; if(index == -1) return 0; else return max(TreeDepth(pTree,pTree[index].lchild),TreeDepth(pTree,pTree[index].rchild)) + 1; } int main() { int n; while(scanf("%d",&n) != EOF) { BTNode *pTree = NULL; if(n>0) { pTree = (BTNode *)malloc(n*sizeof(BTNode)); if(pTree == NULL) exit(EXIT_FAILURE); int i; //输入n个节点的data for(i=0;i<n;i++) { int data1,data2; scanf("%d %d",&data1,&data2); if(data1 != -1) pTree[i].lchild = data1-1; else pTree[i].lchild = -1; if(data2 != -1) pTree[i].rchild = data2-1; else pTree[i].rchild = -1; } } printf("%d",TreeDepth(pTree,0)); } return 0; }
/**************************************************************
Problem: 1350
User: mmc_maodun
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
相关文章
- 【华为OD机试真题 python】 二叉树中序遍历【2022 Q4 | 200分】
- 让整棵二叉树都被相机覆盖到,请问要给二叉树放多少台相机?
- 总结下各种常见树形结构的定义及特点(二叉树、AVL树、红黑树、Trie树、B树、B+树)
- 二叉树的深度优先遍历和广度优先遍历-Python
- 求解二叉树的最短深度-Python
- 剑指offer编程题解法汇总38-二叉树的深度
- 104、【树与二叉树】leetcode ——98. 验证二叉搜索树:递归法[先序+中序+后序]+迭代法(C++版本)
- 90、【树与二叉树】leetcode ——104. 二叉树的最大深度:层次遍历+DFS+子问题分解(C++版本)
- 【数据结构/二叉树】leetcode刷题路线(持续更新)
- 【刷题笔记】之牛客面试必刷TOP101(二叉树的前.中.后.层序遍历+按之字形顺序打印二叉树+二叉树的最大深度+二叉树中和为某一值的路径(一)+二叉搜索树与双向链表+判断是不是二叉搜索树)
- 《数据结构》树和二叉树代码整理(C语言实现)
- 【leetcode】111:二叉树的最小深度
- 【Leetcode】104 :二叉树的最大深度
- [LeetCode] 951. Flip Equivalent Binary Trees 翻转等价二叉树
- [LintCode] Maximum Depth of Binary Tree 二叉树的最大深度
- leetcode算法111.二叉树的最小深度