【代码随想录day16】完全二叉树的节点个数

题目 

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

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

思路 

这题是标标准准得二叉树遍历得题，顺便温习一下3种递归+4种非递归方式。

# 递归前序
def solve(root):
    if not root:
        return 0
    return 1+solve(root.left)+solve(root.right)

# 递归中序
def solve(root):
    if not root:
        return 0
    return solve(root.left)+1+solve(root.right)

# 递归后序
def solve(root):
    if not root:
        return 0
    return solve(root.left)+solve(root.right)+1

# 先序遍历：直接使用一个栈遍历所有节点
def solve(root):
    if not root:
        return 0
    stack = [root]
    res = 0
    while stack:
        now = stack.pop()
        res += 1
        if now.right:
            stack.append(now.right)
        if now.left:
            stack.append(now.left)
    return res

# 中序遍历:需要借助额外指针来遍历，栈只负责存储之前的节点状态
def solve(root):
    if not root:
        return 0
    stack = []
    cur = root
    res = 0
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            res += 1
            cur = cur.right
    return res

# 后序遍历：直接使用一个栈遍历所有节点，先根右左，再逆序，不过这里求得是节点数，不需要再逆序了
def solve(root):
    if not root:
        return 0
    stack = [root]
    res = 0
    while stack:
        now = stack.pop()
        res += 1
        if now.left:
            stack.append(now.left)
        if now.right:
            stack.append(now.right)
    return res

# 层序遍历：借助队列遍历所有节点
from collections import deque
def solve(root):
    if not root:
        return 0
    q = deque([root])
    res = 0
    while q:
        now = q.popleft()
        res += 1
        if now.left:
            q.append(now.left)
        if now.right:
            q.append(now.right)
    return res

当然上面的是普通二叉树的解法。

对于完全二叉树，其中的某些子树必定为满二叉树，而满二叉树的节点个数是有公式的。

高度为h的满二叉树的节点个数是2^h-1，因此可以利用完全二叉树的这个特性进行优化。

递归整棵树，当遇到子树为满二叉树时，直接用公式返回节点个数，而不用真的遍历这个子树的所有节点。如果不为满二叉树，则继续调用countNodes方法判断当前节点的左右子树是否为满二叉树，知道找到满二叉树返回节点个数。 

# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left_num = right_num = 0
        left = root.left
        right = root.right
        while left:
            left_num += 1
            left = left.left
        while right:
            right_num += 1
            right = right.right
        if left_num == right_num:
            return (2<<left_num) - 1
        return self.countNodes(root.left) + self.countNodes(root.right) + 1