往期文章（希望小伙伴們在看這篇文章之前，看一下往期文章）
（1）遞歸、搜索與回溯算法（專題零：解釋回溯算法中涉及到的名詞）【回溯算法入門必看】-CSDN博客
（2）遞歸、搜索與回溯算法（專題一：遞歸）-CSDN博客
?深搜是實現(xiàn)遞歸的一種方式，接下來我們之間從題入手，深入淺出地了解深搜吧！
目錄
1. 計算布爾二叉樹的值
2. 求根結(jié)點到葉結(jié)點的數(shù)字之和
3. 二叉樹剪枝
4. 驗證二叉搜索樹
5. 二叉搜索樹中第k小的元素
??6. 二叉樹的所有路徑
1. 計算布爾二叉樹的值
力扣題目鏈接
?
解析：?
（1）函數(shù)頭設(shè)計
需要根結(jié)點，故函數(shù)頭為：dfs(TreeNode root);
（2）函數(shù)體設(shè)計（無條件相信這個“黑盒”，他能幫你將每個相同的子問題穩(wěn)妥地解決！?。。?/strong>
① 接收左子樹傳過來的值：boolean leftTree = dfs(root.left);? ? ? ?
② 接收右子樹傳過來的值：boolean rightTree = dfs(root.right);
③ leftTree ——> root.val <—— rightTree 得到最終結(jié)果。
（3）遞歸出口
到葉子結(jié)點就是應(yīng)該結(jié)束遞歸，開始回溯。
public boolean evaluateTree(TreeNode root) {
//遞歸出口
//到了葉子結(jié)點
if(root.left == null){
if(root.val == 0)
return false;
else
return true;
}
//開始遞歸
boolean leftTree = evaluateTree(root.left);
boolean rightTree = evaluateTree(root.right);
if(root.val == 2){
return leftTree || rightTree;
}else{
return leftTree && rightTree;
}
}
2. 求根結(jié)點到葉結(jié)點的數(shù)字之和
力扣題目鏈接
解析：
前序遍歷按照根節(jié)點、左?樹、右?樹的順序遍歷?叉樹的所有節(jié)點，通常?于?節(jié)點的狀態(tài)依賴于?節(jié)點狀態(tài)的題?。
在前序遍歷的過程中，我們可以往左右?樹傳遞信息，并且在回溯時得到左右?樹的返回值。遞歸函數(shù)可以幫我們完成兩件事：
（1）將?節(jié)點的數(shù)字與當(dāng)前節(jié)點的信息整合到?起，計算出當(dāng)前節(jié)點的數(shù)字，然后傳遞到下?層進(jìn)?遞
歸；
（2）當(dāng)遇到葉?節(jié)點的時候，就不再向下傳遞信息，?是將整合的結(jié)果向上?直回溯到根節(jié)點。
在遞歸結(jié)束時，根節(jié)點需要返回的值也就被更新為了整棵樹的數(shù)字和。
遞歸函數(shù)設(shè)計：int dfs(TreeNode?root,int num)
（1）返回值：當(dāng)前?樹計算的結(jié)果（數(shù)字和）；
（2）參數(shù)num：遞歸過程中往下傳遞的信息（?節(jié)點的數(shù)字）；
（3）函數(shù)作?：整合?節(jié)點的信息與當(dāng)前節(jié)點的信息計算當(dāng)前節(jié)點數(shù)字，并向下傳遞，在回溯時返回當(dāng)前?樹（當(dāng)前節(jié)點作為?樹根節(jié)點）數(shù)字和。
遞歸函數(shù)流程：
（1）當(dāng)遇到空節(jié)點的時候，說明這條路從根節(jié)點開始沒有分?，返回0；
（2）結(jié)合?節(jié)點傳下的信息以及當(dāng)前節(jié)點的val，計算出當(dāng)前節(jié)點數(shù)字sum；
（3）如果當(dāng)前結(jié)點是葉?節(jié)點，直接返回整合后的結(jié)果sum；
（4）如果當(dāng)前結(jié)點不是葉?節(jié)點，將?sum?傳到左右?樹中去，得到左右?樹中節(jié)點路徑的數(shù)字和，然后相加后返回結(jié)果。
① 將自身的值并入；②??將自己本身的數(shù)字并入后走左子樹；③?將自己本身的數(shù)字并入后走右子樹；④ 左右子樹的結(jié)果，然后向上返回。
public int sumNumbers(TreeNode root) {
return dfs(root,0);//從個位數(shù)開始
}
public int dfs(TreeNode root,int perSum){
//一：將自身的值并入
perSum = perSum * 10 + root.val;
//四：遞歸出口：看看是不是葉子結(jié)點了，如果是，就向上返回
if(root.left == null && root.right == null){
return perSum;
}
//二：走左子樹
int ret = 0;
if(root.left != null){
ret += dfs(root.left,perSum);
}
//三：走右子樹
if(root.right != null){
ret += dfs(root.right,perSum);
}
return ret;
}
3. 二叉樹剪枝
力扣題目鏈接
解析：
后序遍歷按照左?樹、右?樹、根節(jié)點的順序遍歷?叉樹的所有節(jié)點，通常?于?節(jié)點的狀態(tài)依賴于?節(jié)點狀態(tài)的題?。
（1）如果我們選擇從上往下刪除，我們需要收集左右?樹的信息，這可能導(dǎo)致代碼編寫相對困難。然?，通過觀察我們可以發(fā)現(xiàn)，如果我們先刪除最底部的葉?節(jié)點，然后再處理刪除后的節(jié)點，最終的結(jié)果并不會受到影響。
（2）因此，我們可以采?后序遍歷的?式來解決這個問題。在后序遍歷中，我們先處理左?樹，然后處理右?樹，最后再處理當(dāng)前節(jié)點。在處理當(dāng)前節(jié)點時，我們可以判斷其是否為葉?節(jié)點且其值是否為0。如果滿?條件，我們可以刪除當(dāng)前節(jié)點。
? 需要注意的是，在刪除葉?節(jié)點時，其?節(jié)點很可能會成為新的葉?節(jié)點。因此，在處理完?節(jié)點后，我們?nèi)匀恍枰幚懋?dāng)前節(jié)點。這也是為什么選擇后序遍歷的原因（后序遍歷?先遍歷到的?定是葉?節(jié)點）。
? 通過使?后序遍歷，我們可以逐步刪除葉?節(jié)點，并且保證刪除后的節(jié)點仍然滿?刪除操作的要
求。這樣，我們可以較為?便地實現(xiàn)刪除操作，?不會影響最終的結(jié)果。
? 若在處理結(jié)束后所有葉?節(jié)點的值均為1，則所有?樹均包含1，此時可以返回。
遞歸函數(shù)頭設(shè)計：void dfs(TreeNode root)
（1）返回值：?；
（2）參數(shù)：當(dāng)前需要處理的節(jié)點；
（3）函數(shù)作?：判斷當(dāng)前節(jié)點是否需要刪除，若需要刪除，則刪除當(dāng)前節(jié)點。
后序遍歷的主要流程（函數(shù)體）：
（1）遞歸出?：當(dāng)傳?節(jié)點為空時，不做任何處理；
（2）遞歸處理左?樹；
（3）遞歸處理右?樹；
（4）處理當(dāng)前節(jié)點：判斷該節(jié)點是否為葉?節(jié)點（即左右?節(jié)點均被刪除，當(dāng)前節(jié)點成為葉?節(jié)點），并且節(jié)點的值為0：
- 如果是，就刪除掉；
- 如果不是，就不做任何處理。
public TreeNode pruneTree(TreeNode root) {
//遞歸出口
if(root == null){
return null;
}
//判斷左子樹
root.left = pruneTree(root.left);
//判斷右子樹
root.right = pruneTree(root.right);
//判斷
if(root.left == null && root.right == null && root.val == 0){
root = null;
}
return root;
}
4. 驗證二叉搜索樹
力扣題目鏈接
?
解析：
中序遍歷按照左?樹、根節(jié)點、右?樹的順序遍歷?叉樹的所有節(jié)點，通常?于?叉搜索樹相關(guān)題
?。
（1）如果?棵樹是?叉搜索樹，那么它的中序遍歷的結(jié)果?定是?個嚴(yán)格遞增的序列。
（2）因此，我們可以初始化?個?窮?的全區(qū)變量，?來記錄中序遍歷過程中的前驅(qū)結(jié)點。那么就可以在中序遍歷的過程中，先判斷是否和前驅(qū)結(jié)點構(gòu)成遞增序列，然后修改前驅(qū)結(jié)點為當(dāng)前結(jié)點，傳?下?層的遞歸中。?
算法流程：
（1）初始化?個全局的變量prev，?來記錄中序遍歷過程中的前驅(qū)結(jié)點的val；
（2）中序遍歷的遞歸函數(shù)中：
① 設(shè)置遞歸出?：root == null 的時候，返回true；（葉子結(jié)點本身就是一棵二叉搜索樹）
② 先遞歸判斷左?樹是否是?叉搜索樹，?left標(biāo)記；
③ 然后判斷當(dāng)前結(jié)點是否滿??叉搜索樹的性質(zhì)；
? 如果當(dāng)前結(jié)點的val?于prev，說明滿?條件，將prev改為root.val；
? 如果當(dāng)前結(jié)點的val?于等于prev，說明不滿?條件，return false；
最后遞歸判斷右?樹是否是?叉搜索樹，?right標(biāo)記；
（3）只有當(dāng)left和right都是true的時候，才返回true。
long prev = Long.MIN_VALUE;//存放上一個結(jié)點的值
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
//遞歸判斷左子樹
boolean left = isValidBST(root.left);
if(prev < root.val)
prev = root.val;
//判斷當(dāng)前節(jié)點是否為二叉搜索樹，右邊就不需要搞
else
return false;
//剪枝，剪掉右子樹的判斷
if(left == false)
return false;
//遞歸判斷右子樹，告訴父節(jié)點，我不是二叉搜索樹，你也不是
boolean right = isValidBST(root.right);
if(left == true && right == true)
return true;
else
return false;
}
?
5. 二叉搜索樹中第k小的元素
力扣題目鏈接?
?
解析：
中序遍歷 + 計數(shù)器剪枝
我們可以根據(jù)中序遍歷的過程，只需掃描前k個結(jié)點即可。
因此，我們可以創(chuàng)建?個全局的計數(shù)器count，將其初始化為k，每遍歷?個節(jié)點就將count--。直到某次遞歸的時候，count的值等于1，說明此時的結(jié)點就是我們要找的結(jié)果。
int ret = 0;//用來存儲最終結(jié)果
int count;//用來表示要找第幾個結(jié)點
public int kthSmallest(TreeNode root, int k) {
count = k;
dfs(root);
return ret;
}
public void dfs(TreeNode root){
if(root == null)
return;
dfs(root.left);
count--;
if(count == 0){
ret = root.val;
}
dfs(root.right);
}
?
6. 二叉樹的所有路徑
力扣題目鏈接?
?
解析：
使?深度優(yōu)先遍歷（DFS）求解。
路徑以字符串形式存儲，從根節(jié)點開始遍歷，每次遍歷時將當(dāng)前節(jié)點的值加?到路徑中，如果該節(jié)點為葉?節(jié)點，將路徑存儲到結(jié)果中。否則，將"->"加?到路徑中并遞歸遍歷該節(jié)點的左右?樹。
定義?個結(jié)果數(shù)組，進(jìn)?遞歸。遞歸具體實現(xiàn)?法如下：
（1）如果當(dāng)前節(jié)點不為空，就將當(dāng)前節(jié)點的值加?路徑path中，否則直接返回；
（2）判斷當(dāng)前節(jié)點是否為葉?節(jié)點，如果是，則將當(dāng)前路徑加?到所有路徑的存儲數(shù)組paths中；
（3）否則，將當(dāng)前節(jié)點值加上"->"作為路徑的分隔符，繼續(xù)遞歸遍歷當(dāng)前節(jié)點的左右?節(jié)點；
（4）返回結(jié)果數(shù)組；
注：特別地，我們可以只使??個字符串存儲每個狀態(tài)的字符串，在遞歸回溯的過程中，需要將路徑中的當(dāng)前節(jié)點移除，以回到上?個節(jié)點。
具體實現(xiàn)?法如下：
（1）定義?個結(jié)果數(shù)組和?個路徑數(shù)組。
（2）從根節(jié)點開始遞歸，遞歸函數(shù)的參數(shù)為當(dāng)前節(jié)點、結(jié)果數(shù)組和路徑數(shù)組。
① 如果當(dāng)前節(jié)點為空，返回。
② 將當(dāng)前節(jié)點的值加?到路徑數(shù)組中。
③ 如果當(dāng)前節(jié)點為葉?節(jié)點，將路徑數(shù)組中的所有元素拼接成字符串，并將該字符串存儲到結(jié)果
數(shù)組中。
④ 遞歸遍歷當(dāng)前節(jié)點的左?樹。
⑤ 遞歸遍歷當(dāng)前節(jié)點的右?樹。
⑥ 回溯，將路徑數(shù)組中的最后?個元素移除，以返回到上?個節(jié)點。文章來源：http://www.zghlxwxcb.cn/news/detail-807806.html
List<String> ret;
public List<String> binaryTreePaths(TreeNode root) {
ret = new ArrayList<>();
dfs(root,new StringBuffer());
return ret;
}
public void dfs(TreeNode root,StringBuffer curPath){
//起恢復(fù)現(xiàn)場的作用
StringBuffer path = new StringBuffer(curPath);
path.append(Integer.toString(root.val));
if(root.left == null && root.right == null){
ret.add(path.toString());
return;
}
path.append("->");
if(root.left != null) dfs(root.left,path);
if(root.right !=null) dfs(root.right,path);
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-807806.html
到了這里，關(guān)于遞歸、搜索與回溯算法（專題二：深搜）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
