【代码随想录】刷题记录(49)-完全二叉树的节点个数
题目描述：
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
我的作答：
因为题目特别强调是完全二叉树，所以根据完全二叉树的特性来说，不满的肯定是右结点，而除了最下一层是不满的以外，其余的层肯定相等；所以只需要对最下面一层进行处理；
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def countNodes(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
def getNum(node):
if not node:
return 0
left = node.left
right = node.right
leftdepth, rightdepth = 0, 0
while left:
left = left.left
leftdepth += 1
while right:
right = right.right
rightdepth += 1
if leftdepth==rightdepth: #判断子树是否满二叉树
return 2**(leftdepth+1)-1 #深度从0开始所以要加一
leftnum = getNum(node.left) #递归直到左结点为空
rightnum = getNum(node.right) #递归直到右结点空
return leftnum+rightnum+1 #加一是本身的这个结点
return getNum(root)
参考代码：
（1）迭代法
import collections
class Solution:
def countNodes(self, root: TreeNode) -> int:
queue = collections.deque()
if root:
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
result += 1 #记录节点数量
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result（2）精简递归写法（看看得了.jpg）
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)