---
title: "刷題模式: 深度優先搜索（Depth-First Search, DFS）"
description: "Patterns for Coding Questions: Depth-First Search."
image: https://i.imgur.com/Wnnr2qC.png
author: Hsins
tags: LeetCode, Coding Interview
robots:
breaks:
GA:
disqus:
---
# 深度優先搜索（Depth-First Search, DFS）
<p style="text-align: center">
<img src="https://i.imgur.com/Wnnr2qC.png" height=200/>
</p>
> 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。
## 重點整理
- 深度優先搜索（Depth-First Search, DFS）
- 策略：使用 **遞迴（recursion）** 或透過 **堆棧（stack）** 追蹤遍歷過程的父節點
- 題型：
- 樹的自根節點到葉節點遍歷
- 樹的父子路徑相關操作
## 題目匯總
- `0018` Diameter of a Binary Tree
- `0020` Lowest Common Ancestor of a Binary Tree
- `0100` Same Tree
- `0104` Maximum Depth of Binary Tree
- `0110` Balanced Binary Tree
- `0111` Minimum Depth of Binary Tree
- `0112` Path Sum
- `0113` Path Sum II
- `0129` Sum Root to Leaf Numbers
- `0133` Clone Graph
- `0200` Number of Islands
- `0257` Binary Tree Paths
- `0437` Path Sum III
- `0897` Increasing Order Search Tree
## [例題] Binary Tree Path Sum
### 問題
給定一棵二元樹（binary tree）與一個數字 $S$，找出該二元樹中是否存在一條自根節點到葉子節點的路徑，滿足路徑上節點數值總和恰好等於 $S$。
**Example 01**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 10
Output : TRUE
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/Z0X5BIr.png" />
</p>
</td>
</tr>
</table>
**Example 02**
<table>
<tr>
<th>陣列</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 23
Output : TRUE
```
```
Input : S = 16
Output : FALSE
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/X29ykKm.png" />
</p>
</td>
</tr>
</table>
### 題解
由於我們想要 ==搜索自根結點到葉子節點的路徑==，因此採用 **深度優先搜索（Depth-First Search, DFS）** 技巧。
為了遞迴遍歷二元樹，我們可以自根節點開始，呼叫兩個遞迴函數分別處理左子節點和右子節點。具體演算法的步驟如下：
1. 自根結點 `root` 開始進行深度優先搜索
2. 如果當前節點並不是葉子節點，進行以下操作：
- 將路徑和減去當前節點的值，即 `S = S - node.val`
- 呼叫遞迴函數，處理當前節點的左子節點和右子節點，注意子節點須滿足的路經和為前一步驟所得到的 `S = S - node.val`
3. 如果當前節點是葉子節點，且其值滿足路徑和 $S$，即找到滿足條件的路徑，返回 `true`
4. 如果當前節點是葉子節點，但其值不滿足路徑和 $S$ 不同，返回 `talse`
上述步驟如下圖所示：
<p style="text-align: center">
<small>1. 自根結點 <code>root</code> 開始進行深度優先搜索</small>
<img src="https://i.imgur.com/0GEzyzN.png">
<small>2. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 <code>S = 23 - 12 = 11</code></small>
<img src="https://i.imgur.com/lD6Yqha.png">
<small>3. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 <code>S = 11 - 7 = 4</code></small>
<img src="https://i.imgur.com/nKNIXs6.png">
<small>4. 當前節點已為葉子節點，但不滿足 <code>S = 9</code>，故返回 <code>false</code></small>
<img src="https://i.imgur.com/kd0vNuT.png">
<small>5. 節點 <code>7</code> 的左子樹遞迴遍歷完畢，遍歷右子樹；由於右子樹為 <code>null</code>，故返回 <code>false</code></small>
<img src="https://i.imgur.com/CDbfEKI.png">
<small>6. 節點 <code>12</code> 的左子樹遞迴遍歷完畢，遍歷右子樹，遞迴時 <code>S = 23 - 12 = 11</code></small>
<img src="https://i.imgur.com/uscy8ia.png">
<small>7. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 <code>S = 11 - 1 = 10</code></small>
<img src="https://i.imgur.com/niGa6bp.png">
<small>8. 當前節點已為葉子節點，並且滿足 <code>S = 10</code>，故返回 <code>true</code></small>
<img src="https://i.imgur.com/DDPuA8y.png">
<small>9. 左子節點滿足條件，返回 <code>true</code></small>
<img src="https://i.imgur.com/DDPuA8y.png">
<small>10. 右子節點滿足條件，返回 <code>true</code></small>
<img src="https://i.imgur.com/EM2tax7.png">
</p>
### 代碼
#### C++
``` cpp
class TreePathSum {
public:
static bool hasPath(TreeNode *root, int sum) {
if (root == nullptr) return false;
if (root->val == sum && root->left == nullptr && root->right == nullptr) return true;
return hasPath(root->left, sum - root->val) || hasPath(root->right, sum - root->val);
}
}
```
#### Java
``` java
class TreePathSum {
public static boolean hasPaht(TreeNode root, int sum) {
if (root == null) return false;
// if the current node is a leaf and its value is equal to the sum
if (root.val == sum && root.left == null && root.right == null) return true;
// recursively call to traverse the left and right sub-tree
return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
}
}
```
#### JavaScript
``` javascript
const hasPath = (root, sum) => {
// 邊界條件：若為空二元樹，返回 false
if (root === null) return false;
// 判斷當前節點是否為葉子節點，若為葉子節點且滿足路徑和，返回 true
if (root.val === sum && root.left === null && root.right === null) return true;
// 當前節點不滿足條件，繼續遞迴遍歷左右子節點
return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
}
```
#### Python
``` python
def has_path(root, sum):
if root is None:
return False
# if the current node is a leaf and its value is equal to the sum, we've found the path
if root.val == sum and root.left is None and root.right is None:
return True
# recursively call to traverse the left and right sub-tree
return has_path(root.left, sum - root.val) or has_path(root.right, sum - root.val)
```
### 分析
- 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為二元樹中的節點總數
- 空間複雜度：$\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點
## [例題] All Paths for a Sum
### 問題
給定一棵二元樹（binary tree）與一個數字 $S$，找出該二元樹中所有自根節點到葉子節點總和等於 $S$ 的路徑。
**Example 01**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 12
Output : 2
// 1 + 7 + 4 = 12
// 1 + 9 + 2 = 12
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/yeQHo40.png" />
</p>
</td>
</tr>
</table>
**Example 02**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 23
Output : 2
// 12 + 7 + 4 = 23
// 12 + 1 + 10 = 23
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/QODj3Sj.png" />
</p>
</td>
</tr>
</table>
### 題解
這一題遵循 **深度優先搜索（Depth-First Search, DFS）** 策略，注意以下幾點：
- 每次找到滿足條件的路徑時，將其儲存於一個陣列中
- 我們需要遍歷所有路徑，不能在找到第一條路徑時就停止搜索
### 代碼
#### C++
``` cpp
class FindAllTreePaths {
public:
static vector<vector<int>> findPaths(TreeNode *root, int sum) {
vector<vector<int>> allPaths;
vector<int> currentPath;
findPathRecursive(root, sum, currentPath, allPaths);
return allPaths;
}
private:
static void findPathsRecursive(TreeNode *currentNode, int sum, vector<int> ¤tPath, vector<vector<int>> &allPaths) [
if (currentNode == nullptr) return;
currentPath.push_back(currentNode->val);
if (currentNode->val == sum && currentNode->left == nullptr && currentNode->right == nullptr) {
allPaths.push_back(vector<int>(currentPath));
} else {
findPathsRecursive(currentNode->left, sum - currentNode->val, currentPath, allPaths);
findPathsRecursive(currentNode->right, sum - currentNode->val, currentPath, allPaths);
}
currentPath.pop_back();
]
}
```
#### Java
``` java
class FindAllTreePaths {
public static List<List<Integer>> findPaths(TreeNode root, int sum) {
List<List<Integer>> allPaths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<Integer>();
findPathsRecursive(root, sum, currentPath, allPaths);
return allPaths;
}
private static void findPathsRecursive(TreeNode currentNode, int sum, List<Integer> currentPath, List<List<Integer>> allPaths) {
if (currentNode == null) return;
// add the current node to the path
currentPath.add(currentNode.val);
// if current node is a leaf and its value is equal to sum, save the current path
if (currentNode.val == sum && currentNode.left == null && currentNode.right == null) {
allPaths.add(new ArrayList<Integer>(currentPath));
} else {
// traverse the left sub-tree
findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
// traverse the right sub-tree
findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
}
// remove the current node from the path to backtrack
// we need to remove the current node while we're gogin up the recursive call stack
currentPath.remove(currentPath.size() - 1);
}
}
```
#### JavaScript
``` javascript
const findPaths = (root, sum) => {
let allPaths = [];
findPathsRecursive(root, sum, new Deque(), allPaths);
return allPaths;
}
const findPathsRecursive = (currentNode, sum, currentPath, allPaths) => {
if (currentNode == null) return;
// 添加當前節點到路徑中
currentPath.push(currentNode.val);
// 如果當前節點為葉子節點，且滿足路徑和，紀錄當前路徑
if (currentNode.val === sum && currentNode.left === null && currentNode.right === null) {
allPaths.push(currentPath.toArray());
} else {
findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
}
// 將當前節點移出路徑
currentPath.pop();
}
```
#### Python
``` python
def find_paths(root, sum):
all_paths = []
find_paths_recursive(root, sum, [], all_paths)
return all_paths
def find_paths_recursive(current_node, sum, current_path, all_paths):
if current_node is None:
return
current_path.append(current_node.val)
if current_node.val == sum and current_node.left is None and current_node.right is None:
all_paths.append(list(current_node))
else:
find_paths_recursive(current_node.left, sum - current_node.val, current_path, all_paths)
find_paths_recursive(current_node.right, sum - current_node.val, current_path, all_paths)
del current_path[-1]
```
### 分析
- 時間複雜度：$\mathcal{O}(n \log{n})$，其中 $n$ 為二元樹中的節點總數；遍歷所有節點需要花費 $\mathcal{O}(n)$，而在每個葉子節點，需要複製 $\mathcal{O}(\log{n})$ 個結點來儲存其路徑
- 空間複雜度：$\mathcal{O}(n \log{n})$，其中需要 $\mathcal{O}(n)$ 儲存遞迴堆棧（recursion stack）；而儲存所有路徑需要 $\mathcal{O}(n \log{n})$
- 對於二元樹而言，每個葉子節點只有一條路徑可以到達，亦即路徑總數不超過葉子節點數量，因此最大元素數為 $\mathcal{O}(\frac{n}{2}) = \mathcal{O}(n)$
- 每一條路徑包含多個節點，對於平衡二元樹來說，每個葉子節點都位在最大深度，而平衡二元樹的深度是 $\mathcal{O}(\log{n})$
## [例題] Sum of Path Numbers
### 問題
給定一棵二元樹（binary tree），其中節點的值只可能為 `0 - 9`，每一條路徑代表一個數字，計算所有數字的總和。
**Example 01**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Output : 408
// 說明
17 + 192 + 199 = 408
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/Wb0dfF3.png" />
</p>
</td>
</tr>
</table>
**Example 02**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Output : 332
// 說明
101 + 116 + 115 = 332
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/mxenHY9.png" />
</p>
</td>
</tr>
</table>
### 題解
這一題遵循 **深度優先搜索（Depth-First Search, DFS）** 策略，在過程中需要 ==追蹤當前路徑表示的數字==。
那麼我們要如何計算目前路徑所代表的數字呢？比如前面範例中，我們正處在 `7` 這個節點時，當前路徑所代表的數字為 `17 = 1x10 + 7`。
### 代碼
#### C++
``` cpp
class SumOfPathNumbers {
public:
static int findSumOfPathNumbers(TreeNode *root) {
return findRootToLeafPathNumbers(root, 0);
}
private:
static int findRootToLeafPathNumbers(TreeNode *root, int pathSum) {
if (currentNode == nullptr) return 0;
// calculate the path number of the current node
pathSum = 10 * pathSum + currentNode->val;
// if the current node is a leaf, return the current path sum
if (currentNode->left == nullptr && currentNode->right == nullptr) return pathSum;
// traverse the left and right sub-tree
return findRootToLeafPathNumbers(currentNode->left, pathSum) + findRootToLeafPathNumbers(currentNode->right, pathSum);
}
}
```
#### Java
``` java
class SumOfPathNumbers {
public static int findSumOfPathNumbers(TreeNode root) {
return findRootToLeafPathNumbers(root, 0);
}
private static int findRootToLeafPathNumbers(TreeNode currentNode, int pathSum) {
if (currentNode == null) return 0;
// calculate the path number of the current node
pathSum = 10 * pathSum + currentNode.val;
// if current node is a leaf, return the current path sum
if (currentNode.left == null && currentNode.right == null) return pathSum;
// traverse the left and right sub-tree
return findRootToLeafPathNumbers(currentNode.left, pathSum) + findRootToLeafPathNumbers(currentNode.right, pathSum)
}
}
```
#### JavaScript
``` javascript
const findSumOfPathNumbers = (root) => {
return findRootToLeafPathNumbers(root, 0);
}
const findRootToLeafPathNumbers = (currentNode, pathSum) => {
if (currentNode === null) return 0;
// 計算當前節點表示的數字
pathSum = 10 * pathSum + currentNode.val;
// 如果當前節點為葉子節點，返回當前路徑數字
if (currentNode.left === null & currentNode.right === null) return pathSum;
// 遞迴遍歷左右子樹
retrun findRootToLeafPathNumbers(currentNode.left, pathSum) + findRootToLeafPathNumbers(currentNode.right, pathSum);
}
```
#### Python
``` python
def find_sum_of_path_numbers(root):
return find_root_to_leaf_path_numbers(root, 0)
def find_root_to_leaf_path_numbers(current_node, path_sum):
if current_node is None:
return 0
# calculate the path number of the current node
path_sum = 10 * path_sum + current_node.val
# if the current node is a leaf, return the current path sum
if current_node.left is None and current_node.right is None:
return path_sum
# traverse the left and the right sub-tree
return find_root_to_leaf_path_numbers(current_node.left, path_sum) + find_root_to_leaf_path_numbers(current_node.right, path_sum)
```
### 分析
- 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為二元樹中的節點總數
- 空間複雜度：$\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點
## [例題] Path with Given Sequence
### 問題
給定一棵二元樹（binary tree）與一個整數陣列，判斷該整數陣列是不是樹中的一條路徑。
**Example 01**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : [1, 9, 9]
Output : True
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/fqqTjDQ.png" />
</p>
</td>
</tr>
</table>
**Example 02**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : [1, 1, 6]
Output : True
```
```
Input : [1, 0, 7]
Output : False
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/RqqwsA8.png" />
</p>
</td>
</tr>
</table>
### 題解
這一題遵循 **深度優先搜索（Depth-First Search, DFS）** 策略，在過程中需要 ==判斷當前數值是否與陣列元素相符，一但不滿足可以儘早返回==。
### 代碼
#### C++
``` cpp
class PathWithGivenSequence {
public:
static bool findPath(TreeNode *root, const vector<int> &sequence) {
if (root === nullptr) return sequence.empty();
return findPathRecursive(root, sequence, 0);
}
private:
static bool findPathRecursive(TreeNode *currentNode, const vector<int> &sequence, int sequenceIndex) {
if (currentNode == nullptr) return false;
if (sequenceIndex >= sequence.size() || currentNode->val != sequence[sequenceIndex]) return false;
if (currentNode->left == nullptr && currentNode->right == nullptr && sequenceIndex == sequence.size() - 1) return true;
return findPathRecursive(currentNode->left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode->right, sequence, sequenceIndex + 1);
}
}
```
#### Java
``` java
class PathWithGivenSequence {
public static boolean findPath(TreeNode root, int[] sequence) {
if (root == null) return sequence.length == 0;
return findPathRecursive(root, sequence, 0);
}
private static boolean findPathRecursive(TreeNode currentNode, int[] sequence, int sequenceIndex) {
if (currentNode == null) return false;
if (sequenceIndex >= sequence.length || currentNode.val != sequence[sequenceIndex]) retun false;
if (currentNode.left == null && currentNode.right == null && sequenceIndex == sequence.length - 1) return true;
return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
}
}
```
#### JavaScript
``` javascript
const findPath = (root, sequence) => {
if (root === null) return sequence.length === 0;
return findPathRecursive(root, sequence, 0);
}
const findPathRecursive = (currentNode, sequence, sequenceIndex) => {
if (currentNode === null) return false;
const sequenceLength = sequence.length;
if (sequenceIndex >= sequenceLength || currentNode.val !== sequence[sequenceIndex]) return false;
if (currentNode.left === null && currentNode.right === null && sequenceIndex === sequenceLength - 1) return true;
return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1)
}
```
#### Python
``` python
def find_path(root, sequence):
if not root:
return len(sequence) == 0
return find_path_recursive(root, sequence, 0)
def find_path_recursive(current_node, sequence, sequence_index):
if current_node is None:
return False
sequence_length = len(sequence)
if sequence_index >= sequence_length or current_node.val != sequence[sequence_index]:
return False
if current_node.left is None and current_node.right is None and sequence_index == sequence_length - 1:
return True
return find_path_recursive(current_node.left, sequence, sequence_index + 1) or find_path_recursive(current_node.right, sequence, sequence_index + 1)
```
### 分析
- 時間複雜度：$\mathcal{O}(n)$，其中 $n$ 為二元樹中的節點總數
- 空間複雜度：$\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點
## [例題] Count Paths for a Sum
### 問題
給定一棵二元樹（binary tree）與一個數字 $S$，找出該二元樹中所有總和等於 $S$ 的路徑，注意此處的路徑並 **不要求自根結點到葉子節點，只需要遵循父節點到子節點的方向即可**。
**Example 01**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 12
Output : 3
// 7 + 5 = 12
// 1 + 9 + 2 = 12
// 9 + 3 = 12
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/lT116p1.png" />
</p>
</td>
</tr>
</table>
**Example 02**
<table>
<tr>
<th>說明</th>
<th>二元樹</th>
</tr>
<tr>
<td>
```
Input : S = 11
Output : 2
// 7 + 4 = 11
// 1 + 10 = 11
```
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/IIqoKqW.png" />
</p>
</td>
</tr>
</table>
### 題解
這一題遵循 **深度優先搜索（Depth-First Search, DFS）** 策略，注意以下幾點：
1. 必須使用一個陣列追蹤當前路徑，並傳遞給後續的遞迴函數
2. 當遍歷一個節點時，需要執行兩件事：
- 添加當前節點到當前路徑中
- 計算路徑陣列中以當前節點為結束元素的路徑和，若滿足 $S$ 則將計數 `count` 加一
3. 必須遍歷所有路徑，不能在找到條件的路徑時就結束
4. 在返回時必須自路徑中移除當前節點，因為還必須遞迴遍歷其他路徑，需要進行回溯（backtrack）
### 代碼
#### C++
``` cpp
class CountAllPathSum {
public:
static int countPaths(TreeNode *root, int S) {
vector<int> currentPath;
return countPathsRecursive(root, S, currentPath);
}
private:
static int countPathsRecursive(TreeNode *currentNode, int S, vector<int> ¤tPath) {
if (currentNode == nullptr) return 0;
// add the current node to the path
currentPath.push_back(currentNode->val);
int pathCount = 0;
int pathSUm = 0;
// find the sum of all sub-paths in the current path
for (vector<int>::reverse_iterator itr = currentPath.rbegin(); itr != currentPath.rend(); ++itr) {
pathum += *itr;
if (pathSum == S) pathCount++;
}
// traverse the left and right sub-trees
pathCount += countPathsRecursive(currentNode->left, S, currentPath);
pathCount += countPathsRecursive(currentNode->right, S, currentPath);
// remove the current node
currentPath.pop_back();
return pathCount;
}
}
```
#### Java
``` java
class CountAllPathSum {
public static int countPaths(TreeNode root, int S) {
List<Integer> currentPath = new LinkedList<>();
return countPathsRecursive(root, S, currentPath);
}
private static int countPathsRecursive(TreeNode currentNode, int S, List<Integer> currentPath) {
if (currentNode == null) return 0;
// add current node to the path
currentPath.add(currentNode.val);
int pathCount = 0;
int pathSum = 0;
// find the sums of all sub-paths in the current path list
ListIterator<Integer> pathIterator = currentPath.ListIterator(currentPath.size());
while (pathIterator.hasPrevious()) {
pathSum += pathIterator.previous();
if (pathSum == S) pathCount++;
}
// traverse the left and right sub-tree
pathCount += countPathsRecursive(currentNode.left, S, currentPath);
pathCount += countPathsRecursive(currentNode.right, S, currentPath);
// remove current node from the path to backtrack
currentPath.remove(currentPath.size() - 1);
return pathCount;
}
}
```
#### JavaScript
``` javascript
const countPaths = (root, S) => {
return countPathsRecursive(root, S, new Deque());
}
const countPathsRecursive = (currentNode, S, currentPath) => {
if (currentNode === null) return 0;
// add current node to the path
currentPath.push(currentNode.val);
let pathCount = 0;
let pathSum = 0;
// find the sum of all sub-paths in current path
for (let i = currentPath.length - 1; i >= 0; i--) {
pathSum += currentPath[i];
if (pathSum === S) pathCount += 1;
}
// traverse left and right sub-trees
pathCount += countPathsRecursive(currentNode.left, S, currentPath);
pathCount += countPathsRecursive(currentNode.right, S, currentPath);
// remove current node for backtracking
currentPath.pop();
return pathCount;
}
```
#### Python
``` python
def count_paths(root, S):
return count_paths_recursive(root, S, [])
def count_paths_recursive(current_node, S, current_path):
if current_node is None:
return 0
# add current node to the path
current_path.append(current_node.val)
path_count = 0
path_sum = 0
# find the sum of all sub-paths in current path list
for i in range(len(current_path) - 1, -1, -1):
path_sum += current_path[i]
if path_sum == S:
path_count += 1
# traverse left and right sub-tree
path_count += count_paths_recursive(current_node.left, S, current_path)
path_count += count_paths_recursive(current_node.right, S, current_path)
del current_path[-1]
return path_count
```
### 分析
- 時間複雜度：遍歷所有節點需要 $\mathcal{O}(n)$，每一個節點都必須迭代當前路徑，此時：
- 最差狀況在傾斜樹（skewed tree）時的路徑需要 $\mathcal{O}(n)$，故為 $\mathcal{O}(n^2)$
- 最優狀況在平衡樹（balanced tree）時的路徑需要 $\mathcal{O}(\log{n})$，故為 $\mathcal{O}(n \log{n})$
- 空間複雜度：$\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點；除此之外還需要有 $\mathcal{O}(n)$ 儲存 `currentPath`。故 $\mathcal{O}(n + n) = \mathcal{O}(2n) = \mathcal{O}(n)$
## 參考資料
- [Merge Overlapping Intervals | GeeksforGeeks](https://www.geeksforgeeks.org/merging-intervals/)
- [Coding Patterns: Depth First Search (DFS) | emre.me](https://emre.me/coding-patterns/depth-first-search/)
- [Depth First Search Pattern | Astik Anand](https://astikanand.github.io/techblogs/coding-problem-patterns/depth-first-search-pattern)
Sign in with Wallet
Connect another wallet