代码随想录训练营第十六天 | 层序遍历&&完全二叉树的节点个数
222.完全二叉树的节点个数
【思路】
普通二叉树:层序遍历后统计item的个数,累加即可。
完全二叉树:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层(h从1开始),则该层包含1~2^(h-1)个节点。
避免了不必要的节点遍历,节省了时间
判断当前节点的子树是否为满二叉树:判断左右子树的深度是否相同,相同的话即满二叉树,用公式就可以算出满二叉树的节点了。
Java实现
- 普通二叉树解法(层序遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public int countNodes(TreeNode root) {
int num = 0;
if(root == null)return num;
Queue<TreeNode>queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
List<TreeNode>item = new ArrayList<>();
int dep = queue.size();
while(dep>0){
TreeNode node = queue.poll();
item.add(node);
if(node.left!= null)queue.add(node.left);
if(node.right != null)queue.add(node.right);
dep--;
}
if(item.size() >0){
num+=item.size();
}
}
return num;
}
}- 完全二叉树解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public int countNodes(TreeNode root) {
if(root == null)return 0;
TreeNode nodeLeft = root.left;
TreeNode nodeRight = root.right;
int leftDepth=0,rightDepth = 0;
while(nodeLeft!=null){
nodeLeft = nodeLeft.left;
leftDepth++;
}
while(nodeRight != null){
nodeRight = nodeRight.right;
rightDepth++;
}
//如果该二叉树是满二叉树
if(leftDepth == rightDepth ){
return (2 <<leftDepth)-1;
}
//否则就找到是满二叉树
return countNodes(root.left)+countNodes(root.right) + 1;
}
}Go实现
- 普通二叉树解法(层序遍历):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23func countNodes(root *TreeNode) int {
num := 0
if root == nil{
return num
}
curLevel := []*TreeNode{root}
for len(curLevel) >0 {
nextLevel := []*TreeNode{}
for _,node := range curLevel{
if(node.Left != nil){
nextLevel = append(nextLevel,node.Left)
}
if(node.Right != nil){
nextLevel = append(nextLevel,node.Right)
}
}
if(len(curLevel) > 0){
num+=len(curLevel)
}
curLevel = nextLevel
}
return num
}完全二叉树解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22func countNodes(root *TreeNode) int {
if root == nil{
return 0
}
leftNode := root.Left
rightNode := root.Right
leftDepth,rightDepth := 0,0
for leftNode != nil{
leftDepth++
leftNode = leftNode.Left
}
for rightNode != nil{
rightDepth++
rightNode = rightNode.Right
}
if leftDepth == rightDepth {
return (2<<leftDepth) -1
}
return countNodes(root.Left) + countNodes(root.Right)+1
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 林重笑!