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

#方法一：递归法，左右中，后续遍历

# class Solution:

#     def countNodes(self, root: TreeNode) -> int:

#         return self.getNodesNum(root)

#     def getNodesNum(self, cur):

#         if not cur:

#             return 0

#         leftNum = self.getNodesNum(cur.left) #左

#         rightNum = self.getNodesNum(cur.right) #右

#         treeNum = leftNum + rightNum + 1 #中

#         return treeNum    

# class Solution:

#     def countNodes(self,root:TreeNode)->int:

#         if not root:

#             return 0

#         leftnum=self.countNodes(root.left)

#         rightnum=self.countNodes(root.right)

#         treenum=leftnum+rightnum+1

#         return treenum

# #方法一：递归法，精简版

# class Solution:

#     def countNodes(self,root:TreeNode)->int:

#         if not root:

#             return 0

#         return 1 + self.countNodes(root.left) + self.countNodes(root.right)

#方法二：迭代法

# 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

#方法三：递归法，利用完全二叉树的特性

# class Solution:

#     def countNodes(self, root: TreeNode) -> int:

#         #终止条件有两个，一是root为空节点，二是为满二叉树

#         if not root:

#             return 0

#         left = root.left

#         right = root.right

#         leftDepth = 0 #这里初始为0是有目的的，为了下面求指数方便

#         rightDepth = 0

#         while left: #求左子树深度

#             left = left.left

#             leftDepth += 1

#         while right: #求右子树深度

#             right = right.right

#             rightDepth += 1

#         if leftDepth == rightDepth:

#             return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0

#         #其实单层递归逻辑在下面的return中体现

#         leftnum=self.countNodes(root.left)

#         rightnum=self.countNodes(root.right)

#         return leftnum+rightnum+1

# class Solution:

#     def countNodes(self,root:TreeNode)->int:

#         if not root:

#             return 0

#         left=root.left

#         right=root.right

#         leftDepth=0

#         rightDepth=0

#         while left:

#             left=left.left

#             leftDepth+=1

#         while right:

#             right=right.right

#             rightDepth+=1

#         if leftDepth==rightDepth:

#             #注意，减法运算的优先级高于位运算

#             return (2<<leftDepth)-1

#         leftnum=self.countNodes(root.left)

#         rightnum=self.countNodes(root.right)

#         return leftnum+rightnum+1

#方法三，递归法，利用完全二叉树的特性2

# class Solution:

#     def countNodes(self, root: TreeNode) -> int:

#         if not root: return 0

#         count = 1

#         left = root.left; right = root.right

#         while left and right:

#             count+=1

#             left = left.left; right = right.right

#         if not left and not right: # 如果同时到底说明是满二叉树，反之则不是

#             return 2**count-1

#         return 1+self.countNodes(root.left)+self.countNodes(root.right)  

#方法三，递归法，利用完全二叉树的特性3

class Solution: # 利用完全二叉树特性

    def countNodes(self, root: TreeNode) -> int:

        if not root: return 0

        count = 0

        left = root.left; right = root.right

        while left and right:

            count+=1

            left = left.left; right = right.right

        if not left and not right: # 如果同时到底说明是满二叉树，反之则不是

            return (2<<count)-1

        return 1+self.countNodes(root.left)+self.countNodes(root.right)