# Leetcode - Data struct : DFS
###### tags: `Leetcode`
## DFS - 深度優先搜尋的技巧
### (一) . 遞迴存在的概念
1. 遞迴有兩個主要的重點 ： 邊界條件、子問題。
2. 子問題 ： 主要的問題可以分割多個子問題。
3. 邊界條件 ： 子問題結束的條件與點。
### (二) . 邊界檢查 ： 基礎成立於任何樹
- 在任何一個樹進行DFS我們都必須考慮兩個邊界條件 ：
1. 空樹 ： 若根即nullptr，則必須結束。
- 若用單一函式為遞迴時，函式必須有辨別輸入指標是否為空的條件。
- 若用兩個函式為遞迴時，可以在第一個函式去除空樹，在第二個函式，加以進行(多用於輸入和遞迴設計不同時)。
2. 樹葉點 ： 結束於樹葉點本身，或結束於樹葉點下的空指標。
- 結束於空指標造成的原因 ： 在函式前加入空樹的辨別，可以確保接下來不會有記憶體錯誤的問題，但是，如果不加以辨別左右子的存在，就會多執行一次的問題。
- 結束於樹葉點的設計 ： 再繼續進行遞迴之前，先辨別左右子是否存在。
```c=
void dfs(TreeNode* root)
{
if(root==nullptr) // 可以成功地去除空樹的危險。
return ;
cout<<root->val<<" ";
dfs(root->left); // 但是，若左右子是空指標時，會多進行遞迴，
dfs(root->right); // 在新的遞迴函式才會符合終止條件。
return ;
}
```
```c=
void dfs(TreeNode* root)
{
if(root==nullptr) // 可以成功地去除空樹的危險。
return ;
cout<<root->val<<" ";
if(root->left!=nullptr) // 先辨別左右子是否存在
dfs(root->left);
if(root->left!=nullptr) // 可以減少遞迴的function call
dfs(root->right);
return ;
}
```
```c=
void DFS(TreeNode* root)
{
if(root==nullptr)
return ;
dfs(root);
return ;
}
void dfs(TreeNode* root)
{
cout<<root->val<<" ";
if(root->left!=nullptr)
dfs(root->left);
if(root->left!=nullptr)
dfs(root->right);
return ;
}
```
### (三) . 邊界檢查 ： 依要求變動
- 一般的需求通常會跟遍歷扯上關係。
1. 遍歷與否 ： 解的單一或多重。
- 單一解下 ： 找到就可以退出了，不用遍歷所有可能。
- 多重解或不確定單一或多重或無解下 ： 需要遍歷全部，找出解個數的，通常搭配額外記憶體紀錄解的內容及個數。
2. 例 ： root-to-leaf path。
- root-to-leaf path定義 ： 一條必須由根出發到樹葉點的path。
- 可能在半路的節點就已滿足條件，但仍必須繼續遍歷。
### (四) . Stack的回傳形式
- 回傳形式通常與子問題和問題的相關性決定。
1. 回傳```void``` : 問題把子問題的範圍縮小。**在所有可能中尋找滿足的答案(經由遍歷取得得目標)**。
- 二元搜尋。
- 快速排序。
2. 回傳**非**```void``` ： 問題需要子問題的答案。**根問題的答案是所需要的答案**。
- 費氏數列。
- 子集合總和。
## Leetcode - 112 : Path sum
### (一) . 題目
1. 題目 :
```
Given a binary tree and a sum, determine if the tree has a
root-to-leaf path such that adding up all the values along
the path equals the given sum.
Note: A leaf is a node with no children.
```
2. 範例 :
```
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2 which sum is 22.
```
### (二) . 解題 : **DFS，即stack**。
- step1 : 定義問題。
- 觀察題目的輸出入 : 輸出為bool，輸入為root和sum。
- 由輸出入先定義簡單的子問題 : 由root指標為根的樹，是否有滿足sum的path，有回傳true，無回傳false。
- step 2 : 遞迴成立
- 邊界條件 :
- 先考慮剛開始root為nulltr的情況，邊界必須有root==nullptr的處理。
- 若當前節點為nullptr，且sum=0時，則回傳true，若非，回傳false。
- 遞迴執行 : sum先減掉root的value，再回傳給左右子樹辨別。
```c=
bool hasPathSum(TreeNode* root, int sum)
{
if(root==nullptr)
{
if(sum==0)
return true;
else
return false;
}
sum-=root->val;
return hasPathSum(root->right,sum)||hasPathSum(root->left,sum);
}
```
- step 3 : 優化
- 題目要求 : root-to-leaf，意思是必須是要root到某個leaf的path，要考慮兩種例外。
- exception 1 : 不可以由root到其中一個node就停止。
- exception 2 : 不可以只有root。
- 修改演算法 :
- exception 1 : 若滿足sum=0，要辨別是否是葉子點。
- exception 2 : 比較麻煩，要把整個root的辨別，和stack的根的辨別分開
```c=
bool hasPathSum(TreeNode* root, int sum)
{
if(root==nullptr)
return false;
if((sum-=root->val)==0)
{
if(root->right==nullptr&&root->left==nullptr)
return true;
}
return hasPathSum(root->right,sum)||hasPathSum(root->left,sum);
}
```
### (三) . 心得
#### 第一點 : 使用DFS或stack在樹時的邊界注意 :
1. 必須考慮整個樹的root為nullptr時的情形。
2. 結束DFS的地方，**是在葉子點還是葉子點後的nullptr。** 上例 :
- 未修改前的演算法是設定結束於nullptr。
- 修改後的演算法是設定結束於leaf node。
#### 第二點 : 可以先藉由輸出入來定義問題的fumction :
1. 此題的輸入為```TreeNode* root, int sum```，輸出為```bool```。
2. 問題定義為 : 以root為根的樹，有無一個path的和為sum?
## Leetcode - 113 : Path sum 2
### (一) . 題目
1. 題目 :
```
Given a binary tree and a sum, find all root-to-leaf paths
where each path's sum equals the given sum.
```
2. 例子 :
```
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
```
```
Return:
[
[5,4,11,2],
[5,8,4,5]
]
```
### (二) . 解題 : **DFS，即stack**。
- step 1 : 定義問題。
- 看一下問題的輸出入，輸出為一個二維向量，輸出為root和sum。
- 我們不可能每次都回傳一個二維向量，因此單用題目的輸出入應該不好形成一個單一的stack。
- 所以，我們先定義問題 ： **root這個node可不可以使傳入sum變為零，而另外加上一個向量紀錄走過的路徑**。
- 輸入 ： ```dfs(TreeNode* root, int sum ,vector<int> path) ```。
- 輸出 ： ```void```，問題僅需傳遞更新的現象給左右子樹，不用回傳給parent。
- step 2 : 遞迴成立。
- 邊界條件 ： 分成兩個函式執行，
- 空樹 ： 空樹的條件先去除。
- 樹葉點 ： 結束於樹葉點，非空節點。
- 遍歷 ： 因為是root-to-leaf，需要遍歷。
- 要求 ： 當剩餘val為0時，且左右節點為nullptr時。
- 遞迴執行 ： 剩餘val減去此點的值在傳入接下去的節點。
```c=
class Solution {
private:
vector< vector<int> > ans;
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(root==nullptr)
return ans;
vector<int> path;
dfs(root,sum,path);
return ans;
}
void dfs(TreeNode* root ,int val,vector<int> path )
{
val-=root->val;
path.push_back(root->val);
if(val==0)
{
if(root->right==nullptr&&root->left==nullptr)
{
ans.push_back(path);
return ;
}
}
if(root->left!=nullptr)
dfs(root->left,val,path);
if(root->right!=nullptr)
dfs(root->right,val,path);
}
};
```
### (三) . 心得
#### 第一點 ： 把輸入與輸出跟遞迴函式分離
1. 有時候，輸入和輸出不會本身滿足你的遞迴設計。
2. 這時，可以用一個函式為輸出入的介面，自己輸入再設計一個函式在輸出入函式中呼叫。
## Leetcode - 104 : Maximum Depth of Binary Tree
### (一) . 題目
1. 題目 ：
```
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from
the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
```
2. 例子 ：
```
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
```
### (二) . 解題 ： **DFS，即stack**。
- step 1 : 定義問題。
- 觀察輸出入 ： 傳入一個root指標，回傳一個整數，表示最高高度。
- ```int dfs(TreeNode* root)```。
- 由輸出入就定義問題 ： root的最高高度為左右子樹的高度相比最高者。
- step 2 : 遞迴成立。
- 邊界條件 ：
- 空樹 ： root不可以為nullptr。
- 樹葉點 ： 當左右子為nullptr時回傳1。
- 遍歷 ： 需要知道所有左右子樹的高，需遍歷。
- 遞迴執行 ： 回傳左右子數最高高度加一，因為包含自己的高度。
```c=
class Solution {
public:
int maxDepth(TreeNode* root)
{
if(root==nullptr)
return 0;
if(root->left==nullptr&&root->right==nullptr)
return 1;
return 1+max( maxDepth(root->left), maxDepth(root->right));
}
};
```
### (三) . 心得
#### 第一點 ： 不用排斥一開始就要結束在樹葉點。
1. 一開始的寫法 ： 結束於nullptr。比較直觀。
```c=
class Solution {
public:
int maxDepth(TreeNode* root)
{
if(root==nullptr)
return 0;
return max( maxDepth(root->left), maxDepth(root->right))+1;
}
};
```
2. 之後再修改 ： 提前結束。
```c=
class Solution {
public:
int maxDepth(TreeNode* root)
{
if(root==nullptr)
return 0;
if(root->left==nullptr&&root->right==nullptr)
return 1;
return 1+max( maxDepth(root->left), maxDepth(root->right));
}
};
```
## Leetcode - 257 : Binary Tree Paths
### (一) . 題目
1. 題目 ：
```
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
```
2. 例子 ：
```
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
```
### (二) . 解題 ： **DFS，即stack**。
- step1 : 定義問題。
- 觀察輸出入 ： 輸入一個root，輸出一個包含string的陣列。
- ```vector<string> dfs(TreeNode* root)```。
- 每一次都回傳一個字串向量應該不可能，因此，我們分成兩個函式。
- 定義問題 ： root是否為樹葉點，是的話增加path內容並終止遞迴，否的話增加path內容並繼續探索左右子樹。
- 傳入 ： 一個root和一個path。
- 回傳 ： void，因為問題為一層一層的剝開。
- step 2 : 遞迴成立。
- 邊界條件 ：
- 空樹 ： 先去除root為nullptr。
- 樹葉點 ： 若左右子樹為空，停止。
- 遍歷 ： 因為是root-to-leaf，所以要遍歷。
- 遞迴執行 ： 增加path的內容。
```c=
class Solution {
public:
vector<string> allpath;
vector<string> binaryTreePaths(TreeNode* root)
{
if(root==nullptr)
return allpath;
string path;
dfs(root,path);
return allpath;
}
void dfs(TreeNode* root, string path)
{
if(path.empty())
{
path=path+to_string(root->val);
}
else
{
path=path+"->"+to_string(root->val);
}
if(root->left==nullptr&&root->right==nullptr)
{
allpath.push_back(path);
return;
}
if(root->left!=nullptr)
dfs(root->left,path);
if(root->right!=nullptr)
dfs(root->right,path);
return ;
}
};
```
### (三) . 心得
#### 第一點 ： root-to-leaf path 必要遍歷
1. root-to-leaf 的定義 : 一定要從root開始，在leaf結束，不可以在root開始，在root結束。
2. root-to-leaf 既然都要遍歷，那最好可以優化演算法結束在樹葉點，非樹葉點後的空節點。
## Leetcode - 116 : Populating Next Right Pointers in Each Node
#### (一) .
Sign in with Wallet
Connect another wallet