Day7 -104. Maximum Depth of Binary Tree

今日题目：104. Maximum Depth of Binary Tree

刚刚在群组看到在讨论
想说也来写一下哈哈哈哈

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:
Input: root = [1,null,2]
Output: 2

Example 3:
Input: root = []
Output: 0

Example 4:
Input: root = [0]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

思路

使用BFS，以breadth为优先搜索

搜索过的root在进行判断後，自list中删除
如root尚有子点，则将其之子点append回list中

以此recursive後 即可获得depth

My solution

def maxDepth(root):
    
    depth = 0
    q = [root]
    
    if root is None: return 0
    
    while len(q)!=0:
        depth +=1
        for i in range(q[0]):
            if q[0].left:
                q.append(q[0].left)
            if q[0].right:
                q.append(q[0].right)
            del q[0]
    return depth

Result

检讨

在讨论区看到的解答

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

是使用DFS
以深度为优先搜索