# **Leetcode筆記(Maximum Depth of Binary Tree)**
:::info
:information_source: 題目 : Maximum Depth of Binary Tree, 類型 : binary tree , 等級 : easy
日期 : 2023/03/18，2023/05/23，2023/09/11，2024/09/08
:::
### 嘗試
以為root是一個list，可以回傳長度
```python
# 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: Optional[TreeNode]) -> int:
treeLen = len(root)
maxLen = treeLen + 1
times = 0
while maxLen != 1:
maxLen / 2
times += 1
return times
```
2023/05/23
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
```
2023/07/04
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# bfs
if not root:
return 0
q = deque([root])
count = 0
while q:
for _ in range(len(q)):
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
count += 1
return count
```
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left))
```
2023/09/11
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
return self.findHeight(root)
def findHeight(self, node):
if not node:
return 0
rHeight = self.findHeight(node.right)
lHeight = self.findHeight(node.left)
return max(rHeight, lHeight) + 1
```
2024/09/08
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def find_height(node):
if not node:
return 0
l_h = find_height(node.left)
r_h = find_height(node.right)
return max(l_h, r_h) + 1
return find_height(root)
```
---
### **優化**
時間複雜度O(n)，空間複雜度O(n)
```python
# 跌代法
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# 從下面往上看
if not root:
# 這裡的root為一個任一node(看跌代到哪) / 也可能是root本身就為null
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
# 最下面(兩個小孩都是null的會是1 因1+max(0,0))
```
```python
# BFS廣度優先搜尋
# queue
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root]) # 初始化
level = 0
# 由上往下看
while q:
for i in range(len(q)): # 讓左右兩個(q裡面的所有)都跑完
node = q.popleft() # 用node來代替原本的root
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
```
```python
# DFS深度優先搜尋
# stack
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack = [[root, 1]]
# 使用二維list時，如果list[0]會回傳[root, 1]
res = 0 # 為了null
# 由上到下
while stack:
node, depth = stack.pop()
if node: # 若root為null會不通過
res = max(res, depth)
stack.append([node.left, depth + 1])
stack.append([node.right, depth + 1])
# 會先一直往最底部的方向衝去
return res
```
---
**:warning: 錯誤語法**
:::warning
看清楚root是TreeNode形式
:::
**:thumbsup:學習**
:::success
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.
binary tree : 為左右左右的形式，但下面的小孩不一定是完整的，若不適完整，時間複雜度最大為O(n)，是平衡的話最小為O(nlogn)
在 Python 中可以直接使用 collections 模組中的 deque，創造一個雙端佇列（Doubly Ended Queue, Deque）(先進先出)
```python
append(): 新增元素於佇列右側
appendleft(): 新增元素於佇列左側
pop(): 刪除最右側元素
popleft(): 刪除最左側元素
```
list內可以保存不同的資料型態
```python
a = [ ["joe","1234"], ["mary","abcd"], ["david","5678"] ]
print(a[1])
print(a[1][1])
print(a[1][0:2])
#輸出["mary","abcd"]
#輸出 abcd
#輸出["mary","abcd"]
```
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=hTM3phVI6YQ
Provided by. NeetCode
###### tags: `binary tree` `easy` `leetcode`
Sign in with Wallet
Connect another wallet