【题目】
题目描述:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
输入:
第一行输入有n,n表示结点数,结点号从1到n。根结点为1。 n <= 10。
接下来有n行,每行有两个个整型a和b,表示第i个节点的左右孩子孩子。a为左孩子,b为右孩子。当a为-1时,没有左孩子。当b为-1时,没有右孩子。
输出:
输出一个整型,表示树的深度。
样例输入:
32 3-1 -1-1 -1
样例输出:
2
【解析】
通过递归,迭代计算左右子树的深度,+1.
有一个利好的消息是第n个节点数值为n,这样我们就可以利用二维数组来表示树结构。
在程序中利用二维数组来表示树结构,[i][0]为第i个节点的左节点,[i][1]为第i个节点的右节点
【代码】
/*********************************
* 日期:2013-12-06
* 作者:SJF0115
* 题号: 题目1350:二叉树的深度
* 来源:http://ac.jobdu.com/problem.php?pid=1350
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
/*
通过递归,迭代计算左右子树的深度,+1.
在程序中利用二维数组来表示树结构,[i][0]为第i个节点的左节点,[i][1]为第i个节点的右节点
*/
int tree[11][2];
int TreeDepth(int n){
//第n个节点为叶子节点
if(tree[n][0] == -1 && tree[n][1] == -1){
return 1;
}
int left = 0,right = 0;
//迭代计算左右子树的深度
//左子树
if(tree[n][0]!= -1)
{
left = TreeDepth(tree[n][0]);
}
//右子树
if(tree[n][1]!= -1)
{
right = TreeDepth(tree[n][1]);
}
return 1 + max(left,right);
}
int main() {
int i,n,height;
while(scanf("%d",&n) != EOF){
//用二维数组表示二叉树
for(i = 1;i <= n;i++){
scanf("%d %d",&tree[i][0],&tree[i][1]);
}
height = TreeDepth(1);
printf("%d\n",height);
}//while
return 0;
}
分享到:
相关推荐
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
剑指 Offer 55 - I. 二叉树的深度标签:树、深度优先搜索、广度优先搜索、二叉树难度:简单题目大意给定一个二叉树的根节点 root。深度:从根节点到叶
剑指 Offer 55 - I. 二叉树的深度方法一:深度优先搜索(后序遍历)解题思路复杂度分析时间复杂度:O(N)空间复杂度:O(N)代码实现func max
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
第 k 大节点简单树,DFS,二叉搜索树,二叉树剑指 Offer 55 - I. 二叉树的深度简单剑指 Offer 55 - II. 平衡二叉树简单树,DFS,
剑指Offer(Python多种思路实现):二叉树的深度 面试55题: 题目:二叉树的深度 题:输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 ...
翻转单词顺序列,反转链表,斐波那契数列,复杂链表的复制,构建乘积数组,和为s的连续整数序列,和为s的两个数字,滑动窗口的最大值,机器人的运动范围,剑指offer-python实现.docx,矩形覆盖,矩阵中的路径,连续子数组的最大...
示例:给定如下二叉树,以及目标和 sum = 22,返回:思路套用回溯算法的思路设定一个结果数组result来存储所有符合条件的路径设定一个栈stack来存储当
剑指 Offer II 056. 二叉搜索树中两个节点之和标签:树、深度优先搜索、广度优先搜索、二叉搜索树、哈希表、双指针、二叉树难度:简单题目大意给定一个二叉
剑指 Offer II 052. 展平二叉搜索树标签:栈、树、深度优先搜索、二叉搜索树、二叉树难度:简单题目大意给定一棵二叉搜索树的根节点 root。要求:按中
文章目录思路 1:递归 【面试题07】重建二叉树 难度: 中等 限制: 0 <= 节点个数 <= 5000 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。...深度优先遍历,前/中/后序遍历属于深度遍历的一种实现
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15...
剑指 Offer 48. 最长不含重复字符的子字符串 二分查找 278. 第一个错误的版本 哈希表 1. 两数之和 13. 罗马数字转整数 290. 单词规律 动态规划 62. 不同路径 152. 乘积最大子数组 514. 自由之路 背包问题 416. 分割...
leetcode第685题 leetcode-js 力扣js解题记录 树 -> 图论 -> 递归 -> 回溯 ...二叉树的中序遍历 ...剑指 Offer 10- I. 斐波那契数列 剑指 Offer 07. 重建二叉树 剑指 Offer 10- II. 青蛙跳台阶问题 面试题 16
剑指offer 09 最小栈 leetcode 155 栈的压入弹出序列 剑指offer 31 最小的k个数 剑指 Offer 40 数据流的中位数 leetcode 295 递归回溯分治 子集 leetcode 78 全排列 leetcode 46 二叉树与图 路径总和2 leetcode 113 ...
leetcode 答案 leetcode刷题分类基础(前端JavaScript版答案) [TOC] 一、 数组类 1、 04. 二维数组中的查找 2、05. ...2、09....3、30....3、24....DFS深度优先搜索 1、(递归)27. 二叉树的镜像 2、28. 对
该仓库作为个人刷题的题目记录仓库,包含剑指Offer上的全部面试题和LeetCode上的部分题目。 所涵盖的内容有: 剑指offer 75 数组 10 二分查找 9 二叉树,二叉搜索树,红黑树RBTree 44 单链表,哈希表,LRU 33 排序,...
leetcode129 LEETCODE_JAVA 2020.10.22 leetcode344反转字符串 收获:for和while都可以解决这个问题,熟悉一下语法,...剑指offer02 单例模式 单例模式,写了7种实现方式 2020.11.17 剑指offer01 寻找数组中重复的数字
剑指offer 14.链表中倒数第k个结点 题目: 答案: 16.合并两个排序的链表 题目: 答案: 18.二叉树的镜像 题目: 答案: 36.两个链表的第一个公共结点 题目: 答案: 38.二叉树的深度 题目: 答案: 39.平衡二叉树 ...
剑指 offer 程序 = 算法 + 数据结构 算法 算法导论 算法图解 大话数据结构 数据结构与算法分析 算法之美 计算机程序设计艺术 算法与数据结构 算法与数据结构 算法 分治 Divide Conquer 动态规划 贪心 回溯 ...