104/111. 二叉树的最大、最小深度

  1. 先写出通项公式,就是左右孩子都不为空的情况。
  2. 退出条件常为root为空返回0。
  3. 思考只有一个结点(没有左右孩子的时候),左右孩子都是传回0,这个时候带入通项公式是否成立,并获得返回值x。
  4. 考虑只有左孩子的时候(左孩子为一个结点),左孩子传回的应该是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
  • 最小深度bfs解法,判断当前结点是否为叶子结点。
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

推荐阅读更多精彩内容