104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0left = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left,right) + 1111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点
# 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 minDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0left = self.minDepth(root.left)right = self.minDepth(root.right)if not root.left and root.right:return 1+rightif not root.right and root.left:return 1+leftreturn min(left,right)+1要注意：叶子节点是指没有左右子节点的节点。那么就不能无脑return min(left,right)+1 因为如果左边是空右边不是空那么会直接返回1而不是右边的长度
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力解法
# 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 0res = []queue = deque()queue.append(root)while queue:size = len(queue)for i in range(0, size):node = queue.popleft()res.append(node)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return len(res)
普通二叉树写法 递归 卧槽比循环还慢！
# 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 0left = self.countNodes(root.left)right = self.countNodes(root.right)return 1+left+right完全二叉树写法 递归 更tm慢了
# 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 0count = 1left = root.leftright = root.rightwhile left and right:count +=1left = left.leftright = right.rightif not left and not right: # 如果同时到底说明是满二叉树return 2**count-1return 1+self.countNodes(root.left)+self.countNodes(root.right)
