---
# System prepended metadata

title: Leetcode 104. 計算出二元樹的最大深度

---

# Leetcode 104. 計算出二元樹的最大深度

DFS（深度優先搜索）是一種用於遍歷或搜索樹或圖的算法，其特點是盡可能深地搜索樹的分支。不使用遞歸的方式實現 DFS 可以使用棧來存儲節點。

以下是使用棧實現 DFS 的 Python 代碼：

```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:
        if not root:
            return 0
        stack = [(root, 1)]
        max_depth = 0
        while stack:
            node, depth = stack.pop()
            if node:
                max_depth = max(max_depth, depth)
                if node.right:
                    stack.append((node.right, depth + 1))
                if node.left:
                    stack.append((node.left, depth + 1))
        return max_depth
```

在這個實現中，我們使用一個棧來存儲節點和它們的深度。開始時將根節點和深度1入棧，然後重複以下步驟：

1. 從棧中彈出一個節點和它的深度。
2. 如果節點存在，更新最大深度，然後將左右子節點以及它們的深度入棧。

重複執行這個過程直到棧為空，最後返回最大深度。

這種實現方式與遞歸實現相比，不會產生堆棧溢出的問題，因為所有節點都是以迭代的方式處理的，而不是使用遞歸調用。