题目
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例 1:
输入:root = [1,2,3,4,5,6] 输出:6
示例 2:
输入:root = [] 输出:0
示例 3:
输入:root = [1] 输出:1
解题
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def countNodes(self, root: TreeNode) -> int: if not root: return 0 queue = [root] num = 1 while queue: l = len(queue) for _ in range(l): cur = queue.pop(0) left,right = cur.left,cur.right if left: queue.append(left) num+=1 if right: queue.append(right) num+=1 return num
c++解法
class Solution { public: int countNodes(TreeNode* root) { if(!root) return 0; queue<TreeNode*> queue; queue.push(root); int num=0; while(!queue.empty()){ int l=queue.size(); for(int i=0;i<l;i++){ TreeNode* cur=queue.front(); queue.pop(); num++; if(cur->left) queue.push(cur->left); if(cur->right) queue.push(cur->right); } } return num; } };
java解法
class Solution { public int countNodes(TreeNode root) { if(root==null) return 0; Queue<TreeNode> q=new LinkedList<>(); q.add(root); int res=0; while(!q.isEmpty()){ TreeNode cur=q.poll(); if(cur.left!=null) q.add(cur.left); if(cur.right!=null) q.add(cur.right); res++; } return res; } }