【转】http://zhedahht.blog.163.com/blog/static/25411174200732975328975/
题目:输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
例如:输入二元树:
10
/ \
6 14
/ / \
4 12 16
输出该树的深度3。
二元树的结点定义如下:
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
分析:这道题本质上还是考查二元树的遍历。
题目给出了一种树的深度的定义。当然,我们可以按照这种定义去得到树的所有路径,也就能得到最长路径以及它的长度。只是这种思路用来写程序有点麻烦。
我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点,它的深度为1。如果根结点只有左子树而没有右子树,那么树的深度应该是其左子树的深度加1;同样如果根结点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树呢?那该树的深度就是其左、右子树深度的较大值再加1。
上面的这个思路用递归的方法很容易实现,只需要对遍历的代码稍作修改即可。参考代码如下:
///////////////////////////////////////////////////////////////////////
// Get depth of a binary tree
// Input: pTreeNode - the head of a binary tree
// Output: the depth of a binary tree
///////////////////////////////////////////////////////////////////////
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
// the depth of a empty tree is 0
if(!pTreeNode)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(pTreeNode->m_pLeft);
// the depth of right sub-tree
int nRight = TreeDepth(pTreeNode->m_pRight);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
分享到:
相关推荐
为提高矿井提升机盘式制动系统的可靠性与准确分析系统故障的原因,以TE161型液压站为研究对象,构建动态故障树模型,引入深度优先最左遍历方法,模块化处理动态故障树,建立了静态子树和动态子树,基于二元决策图、...
二叉树和二叉搜索树有什么区别 与链接列表相比,在时间复杂度方面可能获得什么? 二叉树的深度,高度和大小是多少 遍历二叉树有哪些不同的遍历方法 什么是完整,完整,完美,平衡的二叉树 文件 任务 0-binary_tree_...
typedef struct与struct的区别、typedef和define的区别、malloc与new的区别、函数指针和指针函数、指针数组和数组指针、写一个函数,完成内存之间的拷贝、判断循环队列空满、二元树的遍历算法、无向图建立、深度优先...
如果我们将密钥存储在二元搜索树中,那么平衡良好的BST将需要与M*log N成比例的时间,其中M是最大字符串长度,N是树中的密钥数。使用Trie,我们可以在O(M)时间内搜索关键字。但是,惩罚是基于Trie存储要求(有关更...
16 演示课 6 二元搜寻树,树的追踪 阅读:12 章 1 到 3 节 17 第九课 二元搜寻树和快速排序法之间的关系;随机二元搜寻树的分析 阅读:12 章 4 节 发《作业 5》 18 第十课 红黑树,循环,插入,删除 阅读:13 章 ...
数据结构堆队列二进制搜索树堆哈希表图形AVL树红黑树不相交集演算法链表遍历链表反向遍历气泡排序选择排序插入排序合并排序堆排序快速排序二元搜寻深度优先搜索广度优先搜索克鲁斯卡尔的吉克斯特拉贝尔曼福特...
深度优先搜索 广度优先搜索 测试 # install dependencies npm install # run all test suite npm run test 在发出拉取请求之前,请确保所有测试均已通过:) 参考 贡献 我知道这套标准并不完美,仍然需要改进。 ...
二元搜寻 一元搜索 数据结构 大批有关数组的更多信息。 单链表 双链表有关链接列表的更多信息。 堆有关堆栈的更多信息。 队列有关队列的更多信息。 哈希表 Python中的简单游戏 猜数字游戏 man子手 剪刀石头布 ...
void dfs(linkmap *maps,int i)//i用来指定深度优先遍历的起始值 { edgenode *pp; printf("%c",maps->maplist[i].element); v[i]=1; pp=maps->maplist[i].firstedge; while(pp) { if(!v[pp->adress]) ...
常见的监督学习算法包括线性回归(用于预测连续值)、逻辑回归(用于预测二元分类问题)、决策树(用于预测分类和回归问题)以及支持向量机(用于分类和回归问题)。 无监督学习算法:模型从未标记的数据中学习。 ...
4. **决策树和随机森林:** 决策树和随机森林是用于分类和回归的机器学习模型。它们通过构建树状结构来进行预测,适用于复杂的非线性关系。 5. **神经网络:** 神经网络是深度学习模型的一种,它可以学习复杂的模式...
我的算法我的算法学习笔记数据结构叠放队列链表BinarySearchTree 组地图eep...二元搜索比特操纵脑筋急转弯违规优先搜索深度优先搜索设计动态编程图形贪婪哈希表堆链表数学段树滑动窗口分类叠串树特里两分球工会发现质量...
主要数据结构的算法(堆栈,队列,树,链表,深度优先(后置顺序)和宽度优先遍历树)。 标准算法(气泡排序,插入排序,合并排序,快速排序,Dijkstra最短路径算法,A *算法,二进制搜索和线性搜索)。
根据公众号机器学习实验室的节奏安排我们预计会涉及以下几个内容的实现:线性回归(一)、逻辑回归(二)、K近邻(三)、决策树值ID3(四)、CART(五)、感知机(六)、神经网络(七)、线性可分支持向量机
二元搜寻 Knuth–Morris–Pratt算法 弗洛伊德·沃歇尔(Floyd-Warshall) 旅行推销员 罗宾·卡普的心律 Dijkstra的算法 一种* 深度优先搜索 广度优先搜索 最小生成树 MST Prim的 MST Kruskal的 楚立·埃德蒙德(有向...
轻松访问和可视化不同的数据结构,包括链表,双链表,树,二叉树,图,堆栈和队列。 我还应该提到,基本数据类的大部分结构都来自多伦多大学的CSC111课程。 我和其他合作者都是多伦多大学的学生,目前正在学习CSC...
二元搜寻 二叉索引树 树 图形 特里(前缀树) 回溯 广度优先搜索 深度优先搜索 分而治之 链表 动态编程 贪婪 数学 采样 设计 支持者 每月捐款支持我们,并帮助我们继续开展活动。 [] 赞助商 成为赞助商,并在我们的...
数据结构位操作数字大批细绳链表堆队列散列堆树图形跳过清单算法种类搜索二元搜寻深度优先搜索广度优先搜索动态编程回溯贪婪的递归特里分而治之数学魔法两指针/滑动窗口慢指针和快指针其他设计版权仅供学习,请拒绝...
二元搜寻 斐波那契数列的矩阵指数 费马定理的模乘乘法逆 尝试 Bellman-Ford算法 Rabin-Karp算法 二进制搜索树 Eratosthenes筛 最大二分匹配 Floyd-Warshall算法 Pollard Rho整数分解 二叉索引树/ BIT 平方根分解 ...
二元级顺序遍历 II ,, 108 将有序数组转换为二叉搜索树 ,, 110 平衡二叉树 ,, 111 二叉树的最小深度 ,, 112 路径和 ,, 118 帕斯卡三角形 ,, 119 帕斯卡三角形 II ,, 121 买卖股票的最佳时机 ,, 122 买卖股票的最佳...