题目简介
104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
559.n叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
222.完全二叉树的节点个数
给你一棵** 完全二叉树** 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2<sup>h</sup> 个节点。
初见思路
- 递归法，很直观；如果想要用迭代法解，可以考虑用层序遍历。
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1
- 层序每层递归寻找子节点最大的深度即可。层序遍历递归比较类似，闲着可以写一下。
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
depth = 0
for i in range(len(root.children)):
depth = max(depth, self.maxDepth(root.children[i]))
return depth + 1
- 迭代法即可，有一个坑是要考虑根节点一边为空的极端情况。
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 极端情况
if (not root.left) and root.right:
return self.minDepth(root.right) + 1
if root.left and (not root.right):
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left),self.minDepth(root.right)) + 1
- 直接层序遍历
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = collections.deque([root])
node_cnt = 0
while queue:
size = len(queue)
node_cnt += size
for _ in range(size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return node_cnt
复盘思路
重点难点
无
今日收获
- 二叉树相关特性
