104. 二叉树的最大深度 [easy]

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

通过次数208,581 | 提交次数282,710

Third Try

2020-07-17

看题解发现还有一种更简洁的递归写法。

class Solution(object):
    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

执行用时：32 ms, 在所有 Python 提交中击败了68.66%的用户
内存消耗：15.4 MB, 在所有 Python 提交中击败了7.69%的用户

Second Try

2020-07-17

顺手写一波DFS版本。

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0 

        max_level = {"val": 0}
        def dfs(level, root, max_level):
            max_level['val'] = max(level, max_level['val'])
            if root and root.left:
                dfs(level + 1, root.left, max_level)
            if root and root.right:
                dfs(level + 1, root.right, max_level)

        dfs(1, root, max_level)
        return max_level['val']

执行用时：20 ms, 在所有 Python 提交中击败了98.95%的用户
内存消耗：15.6 MB, 在所有 Python 提交中击败了7.69%的用户

First Try

2020-07-17

BFS遍历搞定。

同时尝试了一下比较正规的deque双端队列用来做队列，毕竟普通的list在pop(0)的时候可能是O(N)的复杂度。

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

from collections import deque
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0 
            
        queue = deque([[1, root]])
        while len(queue):
            level, node = queue.popleft()
            if node and node.left:
                queue.append([level + 1, node.left])
            if node and node.right:
                queue.append([level + 1, node.right])
        return level 

执行用时：32 ms, 在所有 Python 提交中击败了68.66%的用户
内存消耗：15.5 MB, 在所有 Python 提交中击败了7.69%的用户

104. 二叉树的最大深度 [easy]​

Third Try​

Second Try​

First Try​

104. 二叉树的最大深度 [easy]

Third Try

Second Try

First Try