【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 0res = 0stack = []stack.append(root)while stack:node = stack.pop()res += 1if 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 0def dfs(node):if not node:return 0l_num = dfs(node.left)r_num = dfs(node.right)return l_num + r_num + 1sum = 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 0def get_depth(node):depth = 0while node:depth += 1node = node.leftreturn depthleft_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)