二叉樹深搜：在算法森林中尋找路徑

專欄：算法的魔法世界

個人主頁：手握風云

一、搜索算法

二、回溯算法

三、例題講解

3.1.?計算布爾二叉樹的值

3.2.?求根節點到葉節點數字之和

3.3.?二叉樹剪枝

3.4.?驗證二叉搜索樹

3.5.?二叉搜索樹中第 K 小的元素

3.6.?二叉樹的所有路徑

一、搜索算法

BFS和DFS

? ? ? ? 廣度優先搜索（BFS）和深度優先搜索（DFS）是兩種常用的圖和樹的遍歷算法，遍歷是形式，目的是搜索，在某種形式上，遍歷算法與搜索算法可以等價。

????????BFS 的核心思想是從一個節點開始，逐層遍歷所有可達的節點，直到找到目標節點或遍歷完所有節點。DFS 的核心思想是從一個節點開始，沿著一條路徑盡可能深地搜索，直到無法繼續前進時，再回溯到上一個節點，繼續搜索其他路徑。

暴搜

? ? ? ? 暴力搜索是一種簡單的搜索方式，通過暴力枚舉所有的情況來找出結果，通常基于BFS和DFS實現。暴力搜索通常應用于用于解決那些沒有明顯規律或優化方法的問題，尤其是在數據規模較小時，但有時效率會特別低。

二、回溯算法

? ? ? ? 回溯算法是一種通過遞歸搜索所有可能的候選解來找出所有解的算法，它沒有那么神秘，本質上其實就是DFS。回溯算法通常可用于迷宮求解，如下圖所示，從起點進入并走出迷宮，按照深搜的思路，沿著一條路徑走。如果是死胡同，就回溯走另一條路徑，再次按照DFS，遞歸搜索和回溯找到迷宮出口。如果在搜索之前，我們知道這個答案不是我們想要的，我們就直接可以舍棄，這個過程就叫剪枝。

三、例題講解

3.1.?計算布爾二叉樹的值

????????本題中給出的是完整二叉樹，要么沒有節點，要么左右孩子節點都有。其中葉子節點儲存的是真值，非葉子節點儲存的是邏輯與、或。我們以示例1為例，0合取1，結果為0；0析取1，結果為1，返回真。

????????宏觀角度：從上面的示例中我們可以得出，這棵樹是從下往上推導的。當我們只看根節點時，我們得知道左子樹的值，同時也得知道右子樹的值，然后在根節點這一層進行整合。而關于求出左右子樹的布爾值，與前面的問題是一樣的，只需要傳入一個引用，即可返回布爾值，這就是遞歸方法頭與方法體的設計。當我們遍歷到葉子節點時，不需要判斷它的左右子樹是否為空，只需要進行邏輯運算即可，這同時也是遞歸的出口。

? ? ? ? 細節角度：因為計算過程是從下往上，我們可以看作是二叉樹的后序遍歷。從根節點出發，先去遍歷左子樹，當遇到葉子節點時，返回該節點的布爾值，然后回溯到它的父親節點，然后遍歷右子樹，再回溯父親節點并遍歷自身。

? ? ? ? 完整代碼實現：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean evaluateTree(TreeNode root) {if (root.left == null) {return root.val == 1;}boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? (left || right) : (left && right);}
}

3.2.?求根節點到葉節點數字之和

? ? ? ? 需要計算出從根節點出發到所有葉子節點的每一條路徑所表示的數字，然后將這些數字相加，得到的總和就是最終要求的結果。即要找出二叉樹中所有從根到葉子的路徑所對應的數字，并把它們累加起來。

? ? ? ? 以下圖為例，當我們遞歸到“9”這一層時，我們就需要把“4”先傳進來，計算得到49。再把"49"繼續向下遞歸，計算得到495、491，然后返回，直到返回到根結點。那遞歸的方法頭可以設計兩個參數，一個根結點和一個路徑和presum，返回值為根結點所連接的葉子結點的數字之和。方法體的執行下圖中的4步。遞歸的出口則為遇到葉子結點時，返回路徑之和。

? ? ? ? 完整代碼實現：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumNumbers(TreeNode root) {return dfs(root,0);}private int dfs(TreeNode root,int preSum) {preSum = preSum * 10 + root.val;if (root.left == null && root.right == null) {return preSum;}int ret = 0;if (root.left != null) ret += dfs(root.left,preSum);if (root.right != null) ret += dfs(root.right,preSum);return ret;}
}

3.3.?二叉樹剪枝

? ? ? ? 題目要求移除所有不包含1的子樹，也就是說，如果一個節點沒有任何子節點且其值為0，那么這個節點就應該被刪除。

? ? ? ? 如果我們想剪掉某一棵子樹，必須先知道左右子樹的信息，所以我們一定是要采用后序遍歷來實現。當我們遍歷到某一節點時，如果發現左右子樹均為空，并且節點值為0，那我們就可以把這個節點剪掉。而我們返回它的父親節點時，需要加一個返回值將其置為空，然后繼續判斷。如果節點值為1，那我們就直接返回它的父親節點就可以了。那我們設計遞歸方法的時候，只需傳入一個根節點，然后去遍歷它的左右子樹，根據返回值來判斷是否該剪掉。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {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;}
}

3.4.?驗證二叉搜索樹

? ? ? ? 根據前面學過的知識，對一棵二叉搜索樹進行中序遍歷，得到的結果是一個有序序列，所以我們可以先定義一個全局變量prev，當遍歷到某一個節點時，用prev存儲前一個節點值，如下圖所示，根據中序遍歷，當我們遍歷到1時，將prev賦值為1，然后進行比較，后面的數如果越來越大，那就是二叉搜索樹。當遍歷到19時，會發現19比20小，整棵樹就不是二叉搜索樹。那么我們就可以通過剪枝，省去處理右子樹的過程，直接向上返回一個false。

? ? ? ? 完整代碼實現：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);//剪枝if(left == false) return false;boolean cur = false;if (root.val > prev) cur = true;prev = root.val;boolean right = isValidBST(root.right);return left && cur && right;}
}

3.5.?二叉搜索樹中第 K 小的元素

? ? ? ? 仿照上一題的思路，利用兩個全局變量，其中一個變量是在中序遍歷時充當計數器，另一個變量去標記第K小的結果。進行中序遍歷，當遍歷到第一個節點時，count--，直到count=0時，說明已經到了第k個節點，此時進行剪枝，把ret更新為17，無需遍歷其它子樹。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int count;int ret;public int kthSmallest(TreeNode root, int k) {count = k;InOrder(root);return ret;}public void InOrder(TreeNode root) {if (root == null || count == 0) return;InOrder(root.left);count--;if (count == 0) ret = root.val;if (count == 0) return;InOrder(root.right);}
}

3.6.?二叉樹的所有路徑

????????給定一個二叉樹的根節點，然后找出所有從根節點到葉子節點的路徑。每條路徑都應該以字符串的形式返回，路徑中的節點值之間用箭頭“->”連接。

? ? ? ? 我們先弄一個字符串變量path，在進行前序遍歷的時候，記錄每個路徑的字符串，當遇到葉子節點時，丟進順序表List<String> ret中。但如果我們遍歷完一條路徑后，回溯就會出現問題，比如我們遍歷完"1->2->4"，回溯到節點2時，也會返回這個結果，所以我們還需要進行恢復現場的操作，把字符4移除。當我們把節點2處理完返回到節點1時，我們需要移除的是"2->"，所以這個過程就會非常麻煩。我們可以把這個變量放在遞歸方法的參數里，那我們的方法頭就可以設計成DFS(root,path)。當遞歸方法執行的時候，如果是葉子節點，不需要加上"->"；如果不是葉子節點，需要加上"->"。當某個節點的左子樹為空而右子樹不為空，那就不需要執行DFS(root.right,path)，直接返回。

? ? ? ? 完整代碼實現：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();DFS(root,new StringBuffer());return ret;}public void DFS(TreeNode root,StringBuffer _path) {StringBuffer path = new StringBuffer(_path);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);}
}