This page looks best with JavaScript enabled

Leetcode 104 Maximum Depth of Binary Tree

 · 

Summary

輸入一個二元樹,回傳其深度
可行作法:

  • BFS 作法: 一層一層跑,紀錄次數,直到最後一層
  • DFS 作法:搭配 recursion,code 很短

Problem

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

My Solution

先來做寫起來不方便的 bfs

BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        re, queue = 0, [root]
        while queue:
            tmp = []
            for q in queue:
                tmp += [ _ for _ in [q.left, q.right] if _ ]
            re, queue = re+1, tmp
        return re

DFS

故意全部塞進一行

1
2
3
4
5
6
7
8
9
# Definition for a binary tree node
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return root and 1+max(self.maxDepth(root.left), self.maxDepth(root.right)) or 0