前往此题

深度优先

用递归的话比较好解, 借助这套公式max(l + r) + 1。l与r代表当前递归左右子树的深度。也就是说在每次递归都会返回深度+1，最终比较深的那一边就是最终答案。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(h) 取决于树的深度

广度优先

BFS的思路其实和DFS一样，用队列的方式写同样也能实现。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        deep = 0
        queue = [root]
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.pop(0)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            deep += 1
        return deep

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N) 最坏情况下