【leetcode】222. 完全二叉树的节点个数

题目

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

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

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

题解

1. 迭代

# 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
        """
        if not root:
            return 0
        res = 0
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            res += 1
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
        

2. 递归

# 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
        """
        if not root:
            return 0
        def dfs(node):
            if not node:
                return 0
            l_num = dfs(node.left)
            r_num = dfs(node.right)
            return l_num + r_num + 1
        sum = dfs(root)
        return sum
   

3. 利用完全二叉树的性质

1. 左子树和右子树层数相同，则左边满，计算右边
2. 左子树和右子树层数不同，左边可能不满，右边满

# 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
        """
        if not root:
            return 0

        def get_depth(node):
            depth = 0
            while node:
                depth += 1
                node = node.left
            return depth

        left_depth = get_depth(root.left)
        right_depth = get_depth(root.right)

        if left_depth == right_depth:
            return (1 << left_depth) + self.countNodes(root.right)
        else:
            return (1 << right_depth) + self.countNodes(root.left)