代码随想录算法训练营第十三天 | leetcode：二叉树的最大深度,最小深度,完全二叉树的节点个数
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 104. 二叉树的最大深度
解题方法
- 使用层序遍历法，在每层遍历的时候增加计数即可。
code
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root) {
//深度计数
$deep = 0;
if($root == null) return 0;
$queue = new SplQueue();
$queue->enqueue($root);
while(!$queue->isEmpty()){
$size = $queue->count();
//每层计数++
$deep++;
while($size--){
$node = $queue->dequeue();
if($node->left != null) $queue->enqueue($node->left);
if($node->right != null) $queue->enqueue($node->right);
}
}
return $deep;
}
}Problem: 111. 二叉树的最小深度
需要注意的地方
需要使用标志位跳出双重while循环。
解题方法
- 使用层序遍历法，在每层遍历加入新的左右孩子入队列时，判断第一个左右孩子都为空的情况跳出循环即可。遍历到第一个左右孩子都为空代表，此时节点就是最小深度的叶子节点。
code
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function minDepth($root) {
$deep = 0;
if($root == null) return $deep;
$queue = new SplQueue();
$queue->enqueue($root);
//跳出循环标志位
$end = 0;
while(!$queue->isEmpty()){
$size = $queue->count();
$deep++;
print_r($deep."\r\n");
while($size--){
$node = $queue->dequeue();
//左右子树都为空的情况直接跳出循环
if($node->left == null && $node->right == null){
//设置循环标志位，跳出内层循环
$end = 1;
break;
}
//一定需要再判断孩子节点是否为空，否则孩子节点为空队列加入了null，第二层就会break退出。
if($node->left != null) $queue->enqueue($node->left);
if($node->right != null) $queue->enqueue($node->right);
}
//监听内层循环，跳出外层循环
if($end == 1) break;
}
return $deep;
}
}Problem: 222. 完全二叉树的节点个数
解题方法
- 使用层序遍历法，在每层遍历的时候增加节点总计数即可。
code
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function countNodes($root) {
//总计数
$count = 0;
if($root == null) return 0;
$queue = new SplQueue();
$queue->enqueue($root);
while(!$queue->isEmpty()){
$size = $queue->count();
//每层都叠加总计数
$count += $size;
while($size--){
$node = $queue->dequeue();
if($node->left != null) $queue->enqueue($node->left);
if($node->right != null) $queue->enqueue($node->right);
}
}
return $count;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号