- 先写出通项公式，就是左右孩子都不为空的情况。
- 退出条件常为root为空返回0。
- 思考只有一个结点(没有左右孩子的时候)，左右孩子都是传回0，这个时候带入通项公式是否成立，并获得返回值x。
- 考虑只有左孩子的时候(左孩子为一个结点)，左孩子传回的应该是x，右孩子传回的是0，带入通项公式，考虑是否成立。
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
- 最小深度，注意其中一个孩子不为None，另一个孩子为None的情况
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and root.right:
return self.minDepth(root.right) + 1
if not root.right and root.left:
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
queue = [root]
level = 1
while queue:
n = len(queue)
for i in range(n):
cur = queue.pop(0)
if not cur.left and not cur.right:
return level
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
level += 1
