一、题目描述

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

示例 1:

输入:root = [1,2,3,4,5,6]
输出:6

示例 2:

输入:root = []
输出:0

示例 3:

输入:root = [1]
输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 10^4
  • 题目数据保证输入的树是 完全二叉树

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 完全二叉树的节点个数( LeetCode 222 ):https://leetcode-cn.com/problems/count-complete-tree-nodes/submissions/
class Solution {
    public int countNodes(TreeNode root) {
        // 边界情况处理
        if (root == null) return 0;

        // 设置一个队列,用来存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<>();

        // 队列添加二叉树的根节点
        nodeQueue.add(root);

        // 设置 result 用来保存输出结果
        int result = 0;

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while (!nodeQueue.isEmpty()) {

            // 用来记录 queue 的长度,即每层节点的个数
            int size = nodeQueue.size();

            // 使用 for 循环,将 nodeQueue 中的元素统计
            for (int i = 0; i < size; i++) {

                // 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点      
                TreeNode curNode = nodeQueue.poll();

                // 说明此时统计了一个节点,结果 +1
                result++;

                // 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                if (curNode.left != null){
                    nodeQueue.add(curNode.left);
                } 

                // 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中    
                if (curNode.right != null){
                    nodeQueue.add(curNode.right);
                }

            }
        }

        // 返回 result
        return result;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 完全二叉树的节点个数( LeetCode 222 ):https://leetcode-cn.com/problems/count-complete-tree-nodes/submissions/
class Solution {
public:
    int countNodes(TreeNode* root) {
        // 边界情况处理
        if (root == NULL) return 0;

        // 设置一个队列,用来存储二叉树中的元素
        queue<TreeNode*> nodeQueue;

        // 队列添加二叉树的根节点
        nodeQueue.push(root);

        // 设置 result 用来保存输出结果
        int result = 0;

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while (!nodeQueue.empty()) {

            // 用来记录 queue 的长度,即每层节点的个数
            int size = nodeQueue.size();

            // 使用 for 循环,将 nodeQueue 中的元素统计
            for (int i = 0; i < size; i++) {

                // 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点      
                TreeNode* curNode = nodeQueue.front();
                nodeQueue.pop();

                // 说明此时统计了一个节点,结果 +1
                result++;

                // 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                if (curNode->left != NULL){
                    nodeQueue.push(curNode->left);
                } 

                // 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中    
                if (curNode->right != NULL){
                    nodeQueue.push(curNode->right);
                }

            }
        }

        // 返回 result
        return result;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 完全二叉树的节点个数( LeetCode 222 ):https://leetcode-cn.com/problems/count-complete-tree-nodes/submissions/
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # 边界情况处理
        if not root :
          return 0

        # 设置一个队列,用来存储二叉树中的元素
        nodeQueue = collections.deque([])


        # 队列添加二叉树的根节点
        nodeQueue.append(root)

        # 设置 result 用来保存输出结果
        result = 0

        # 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while nodeQueue:

            # 用来记录 queue 的长度,即每层节点的个数
            size = len(nodeQueue)

            # 使用 for 循环,将 nodeQueue 中的元素统计
            for _ in range(size):

                # 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点      
                curNode = nodeQueue.popleft()

                # 说明此时统计了一个节点,结果 +1
                result += 1

                # 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                if curNode.left :
                    nodeQueue.append(curNode.left)

                # 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中    
                if curNode.right :
                    nodeQueue.append(curNode.right)

        # 返回 result
        return result

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注