返回

LeetCode 0222.完全二叉树的节点个数

完全二叉树的节点个数

LeetCode222. 完全二叉树的节点个数

题目描述

给你一棵完全二叉树的根节点 root ,求出该树的节点个数。

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~2 h 个节点。

示例:

思路

迭代法,遍历模板稍稍修改一下,记录遍历的节点数量就可以了。

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func countNodes(root *TreeNode) int {
    // 设置节点计数器
    count := 0
    if root == nil {
        // 根节点为空
        return count
    }
    // 用切片模拟队列
    queue := make([]*TreeNode, 0)
    // 根节点入队,节点数+1
    queue = append(queue, root)
    count++
    // 遍历二叉树
    for len(queue) > 0 {
        // 记录当前层节点数
        l := len(queue)
        // 遍历一层
        for i := 0; i < l; i++ {
            // 若当前节点有子节点,则入队
            if queue[0].Left != nil {
                // 左子节点入队,节点数+1
                queue = append(queue, queue[0].Left)
                count++
            }
            if queue[0].Right != nil {
                // 右子节点入队,节点数+1
                queue = append(queue, queue[0].Right)
                count++
            }
            // 当前节点出队
            queue = queue[1:]
        }
    }
    // 返回层次遍历的节点数
    return count
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy