这个是常见的对二叉树的操作。总结一下:
设节点的数据结构,如下:
treenode(char _val) {
this.val = _val;
}
}
1.二叉树深度
这个可以使用递归,分别求出左子树的深度、右子树的深度,两个深度的较大值+1即可。
2.二叉树宽度
使用队列,层次遍历二叉树。在上一层遍历完成后,下一层的所有节点已经放到队列中,此时队列中的元素个数就是下一层的宽度。以此类推,依次遍历下一层即可求出二叉树的最大宽度。
queue<treenode> queue = new arraydeque<treenode>();
int maxwitdth = 1; // 最大宽度
queue.add(root); // 入队
while (true) {
int len = queue.size(); // 当前层的节点个数
if (len == 0)
break;
while (len > 0) {// 如果当前层,还有节点
treenode t = queue.poll();
len--;
if (t.left != null)
queue.add(t.left); // 下一层节点入队
if (t.right != null)
queue.add(t.right);// 下一层节点入队
}
maxwitdth = math.max(maxwitdth, queue.size());
}
return maxwitdth;
}
如对本文有疑问, 点击进行留言回复!!
unity的错误解决办法:NullReferenceException: Object reference not set to an instance of an object;tiny proje
Hadoop 之 HDFS (HDFS 数据流的 读写 流程)
听说你一读Spring源码就懵逼?我帮你把架子搭好了,你填就行!
首席架构师推荐:金融保险领域数字化转型实践--如何优雅地修改业务中台中分层应用Maven多模块的版本号?(命令导入式)
[JVM学习之路]一、初识JVM,了解其结构、模型及生命周期
网友评论