题目
题目标题:
求二叉树的宽度和深度
给定一个二叉树,获取该二叉树的宽度和深度。
例如输入
a
/ \
b c
/ \ / \
d e f g
返回3.
接口说明
原型:
int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
输入参数:
head 需要获取深度的二叉树头结点
输出参数(指针指向的内存区域保证有效):
pulWidth 宽度
pulHeight 高度
返回值:
0 成功
1 失败或其他异常
练习阶段:
中级
代码
#include <iostream>
#include "OJ.h"
#include <string>
#include <queue>
using namespace std;
int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight){
if(&head == NULL || pulWidth == NULL || pulHeight == NULL){
return 1;
}
int maxWidth = 0;
int curWidth = 0;
int height = 0;
BiNode* root = &head;
queue<BiNode*> curQueue;
queue<BiNode*> nextQueue;
curQueue.push(root);
while(!curQueue.empty()){
++height;
curWidth = 0;
while(!curQueue.empty()){
++curWidth;
BiNode* node = curQueue.front();
curQueue.pop();
if(node->left != NULL){
nextQueue.push(node->left);
}
if(node->right != NULL){
nextQueue.push(node->right);
}
}
if(curWidth > maxWidth){
maxWidth = curWidth;
}
swap(curQueue,nextQueue);
}
*pulWidth = maxWidth;
*pulHeight = height;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
华为机试代码,各种问题,链表合集,二叉树合集,背包问题等 比较难的问题,还有简单的加减乘除等
私信博主免费获取真题解析以及代码
私信博主免费看所有华为OD真题、考试报告、手撕代码、面试记录
华为机考真题,本人亲身经历,对即将参加华为机试的同学有极大的帮助。
【免费题库】华为OD机试 - 数组二叉树(Java & JS & Python & C & C++).html
二叉树的遍历通常有四种主要方法:前序遍历(Pre-order Traversal)、中序遍历(In-order Traversal)、后序遍历(Post-order Traversal)和层序遍历(Level-order Traversal 或 Breadth-First Search, BFS)。...
华为OD机试 - 二叉树的广度优先遍历(Java & JS & Python & C & C++).html付费专栏内容,免费下载,多种语言解法
私信博主免费获取真题解析以及代码
私信博主免费看所有华为OD真题、考试报告、手撕代码、面试记录
私信博主免费看所有华为OD真题、考试报告、手撕代码、面试记录
①初始化一个辅助队列 ②根结点入队 ③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话) ④重复③直至队列为空 ①初始化一个辅助队列
华为校园招聘笔试题大全是面向应届毕业生的招聘考试,涵盖了计算机科学和信息技术的多个领域。下面是该考试题库的知识点总结: 1. 静态变量的用途: 静态变量有多种用途,包括: * 在函数体内,静态变量可以维持其...
平衡二叉树是一种特殊的二叉树,左右子树都是平衡二叉树,且左右子树的深度差值的绝对值不大于 1。 6. 堆栈溢出的原因: 堆栈溢出通常是由于没有回收垃圾资源所致。 7. 无法声明为虚函数的函数: 构造函数不能声明...
js代码-二叉树广度优先遍历
华为 1.static有什么用途?(请至少说明两种) 1)在函数体,一个被声明为静态的变量在这一函数被调用过程中维持其值不变。 2) 在模块内(但在函数体外)...最新的统计华为面试题.无论面试还是学习指导都具有重要意义.
剑指offer面试题(7)——重建二叉树整体工程代码,C++语言实现。
左右子树都是平衡二叉树 且左右子树的深度之差的绝对值不超过1。 6.堆栈溢出一般是由什么原因导致的? 没有回收垃圾资源。 7.什么函数不能声明为虚函数? (Constructor)构造函数不能声明为虚函数。 8.冒泡排序...
1.static有什么用途?(请至少说明两种) 1)在函数体,一个被声明为静态的变量在这一... 左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于1。 6.堆栈溢出一般是由什么原因导致的? 没有回收垃圾资源。
本文档是华为校园招聘软件测试笔试题的详细信息汇总,涵盖了软件基础题、数据结构编程题、数据库题等多个方面,考察候选人的软件工程知识、数据结构知识、数据库知识和编程能力等。 此外,我们还可以总结出一些笔试...