文章目錄
-
-
- 一. 前言
- 二. 關于遞歸
- 三. 二叉樹的深度
-
- ① 最大深度 LeetCode 104
- ② 最小深度 LeetCode 111
- 四. 樹的周遊
-
- ① 二叉樹的前序周遊 LeetCode 144
- ② 二叉樹的中序周遊 LeetCode 94
- ③ 二叉樹的後序周遊 LeetCode 145
- ④ 二叉樹的層序周遊 LeetCode 102
- ⑤ 二叉樹的垂序周遊 LeetCode 987
- 五. 根據兩種周遊來還原樹的結構
-
- ①前序 + 中序 LeetCode 105
- ② 後序 + 中序 LeetCode 106
- 六. 左葉子之和
- 七. 路徑和
-
- ① 路徑總和 LeetCode 112.
- ② 路徑總和 Ⅱ LeetCode 113.
- ③ 路徑總和 Ⅲ LeetCode 437.
- 八. 二叉搜尋樹BST
-
- ① 修剪二叉搜尋樹 LeetCode 669.
- ② 二叉搜尋樹中第K小的元素 LeetCode 230.
- ③ 把二叉搜尋樹轉換成累加樹 LeetCode 538.
- ④ 二叉搜尋樹的最近公共祖先 LeetCode 235
- ⑤ 二叉樹的最近公共祖先 LCA問題 LeetCode 236
-
一. 前言
樹也是一種常見的資料結構，在算法題裡最常見的就是數組，連結清單，哈希表以及樹。前三者平時很常用到，是以也不會覺得太難。樹如果剛開始沒有練習，會覺得很難，但在經過一定的練習和總結之後，會覺得樹的題目也是比較容易解決的。這裡目前隻記錄了比較常見且典型的樹型題目，一些奇形怪狀的樹題暫時不考慮。
二. 關于遞歸
遞歸是一種常見的解題方法，主要特征為反複調用自身。遞歸會讓代碼看起來很簡潔，邏輯也很清晰，但有時候也會造成大量的重複計算。二叉樹跟連結清單是很适合進行遞歸的資料結構，因為它們的資料就像一段一段的，遞歸可以使我們把思考的重點放在“目前層次的遞歸應該做什麼”，而不必陷入整個複雜資料結構的複雜思考。
遞歸的核心是反複調用自身，我們有3個點需要重點思考：
①既然是反複調用自身，那麼什麼時候結束？即我們需要尋找遞歸的終止條件
②應該傳回什麼？對于第一層遞歸，傳回值就是最終結果。同時第一層需要調用第二層的遞歸結果，那麼第二層需要傳回給上一級（也就是第一層）什麼樣的結果？
③每一層遞歸應該做什麼？也就是目前層次的遞歸，需要進行什麼邏輯？完成什麼任務?
對于接下來的樹題，我們都會優先思考遞歸解題模闆，然後再尋找疊代式的解題方法。
三. 二叉樹的深度
① 最大深度 LeetCode 104
描述： 給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。題目連結
分析：先以遞歸的思路來思考：
① 如果要用遞歸，什麼時候結束？顯然，當root為null的時候，就不必繼續遞歸了，此時直接傳回0。
② 應該傳回什麼？其實每一層的傳回值都是一樣的，因為遞歸是調用自身，是以不存在說第一層傳回的是xxx概念，而其他層傳回的是yyy概念。那麼第一層傳回什麼呢，就是傳回根節點root的深度。是以後續的每一層也是一樣的，就是傳回以目前結點為root的樹的深度。
③每一層遞歸應該做什麼？終止條件，傳回值我們都已經想好了，這時候就是需要中間的邏輯。在目前層，我們需要獲得root的深度，這時候我們要遞歸下去，就是把root.left和root.right成為下一層遞歸的根節點，這樣我們就求得root的左子樹深度，以及右子樹的深度，然後它們二者較大的值加上root本身深度（也就是1），就是root的最大深度。是以 root的深度 = 1 + max（root.left的深度， root.right的深度）。
這就是遞歸的優雅之處，我們隻需要考慮目前層的邏輯，對于目前層，root的深度隻要考慮root.left的深度以及root.right的深度，至于root.left的結構是什麼，是否為null，root.left的最大深度是root.left.left還是root.left.right？這些在下一層就會變成和目前層一樣的邏輯，我們無須考慮。于是我們可以獲得代碼：
代碼：
class Solution {
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}
}
如果你更熟練，會發現leftDepth與rightDepth變量也是可以省略的，這時候就能寫出更簡潔的代碼：
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 :
1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
一行解決！相信你已經體會到了遞歸的美妙之處。當然，其實這裡還是會産生了很多重複運算，是以可以使用一個Map來存儲資料，提升效率。不要看LeetCode上效率更慢，那是測試用例的問題，如果存在一個巨型二叉樹，上面的代碼需要很長的時間，而使用Map會提升不少效率。
使用 Map作備忘錄的遞歸代碼：
class Solution {
public int maxDepth(TreeNode root) {
Map<TreeNode, Integer> map = new HashMap<>();
int res = helper(root, map);
return res;
}
public int helper(TreeNode root, Map<TreeNode, Integer> map) {
if (root == null)
return 0;
if (map.containsKey(root))
return map.get(root);
int left = helper(root.left, map);
int right = helper(root.right, map);
int res = 1 + Math.max(left, right);
map.put(root, res);
return res;
}
}
遞歸解法很簡單，如果不允許用遞歸呢，如果一定要用疊代的方法，應該如何編碼？這個我們等會再說。
② 最小深度 LeetCode 111
描述： RT。題目連結
分析：最大深度的遞歸結束是當結點為null的時候，而最小深度則是遇到第一個葉子結點就傳回，同時要取min而不是max，于是很容易寫出這種代碼：
class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
}
然後就錯了，因為max我們可以確定肯定會選最大的子樹長度，而min可能會選擇了空子樹，使得結果出錯，比如測試用例[1, 2]，這時候右子樹深度為0，答案就變成了1，而不是2，是以隻有當root.left，root.right不為null的時候才放進去遞歸。當然，最開始的判斷root是否為null還是不能省略的，因為可能輸入的參數就剛好是root。
正确的代碼：
class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
if (root.left != null && root.right == null)
return 1 + minDepth(root.left);
if (root.right != null && root.left == null)
return 1 + minDepth(root.right);
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
// 如果都為null, 也不會影響結果
}
}
四. 樹的周遊
描述：樹的周遊是很常見的題，包括前序周遊，中序周遊，後序周遊，層序周遊，垂序周遊（前三種比較常見）。然後還存在根據前序與中序還原樹，後序與中序還原樹等等的題目。是以我們先從樹的周遊開始總結（上一題主要解釋一下遞歸的過程）。值得注意的是，有一些題目因為遞歸解法太過簡單，是以有時候題目會要求“不要用遞歸，而是用疊代”，一下子就使得題目難度增加不少。是以這裡會盡量通過兩種方法來解決。
① 二叉樹的前序周遊 LeetCode 144
描述：RT。題目連結
遞歸解法：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preOrder(root, list);
return list;
}
public void preOrder(TreeNode root, List<Integer> list) {
if (root == null) // 遞歸結束
return;
list.add(root.val); // 目前層的操作
preOrder(root.left, list); // 遞歸
preOrder(root.right, list); // 遞歸
}
}
如果要把遞歸解法轉換成疊代解法，一般都可以通過棧來實作，因為遞歸實質也是使用棧，隻是遞歸壓棧的并不是數值對象，而是整個方法。是以才會有“遞歸棧"這種說法，在畫出遞歸的過程時，實際上就是畫遞歸棧。是以我們這裡通過棧來放置樹的結點，優先push右節點，因為後進先出，前序周遊的順序是：根節點->左節點->右節點，是以先push右節點，再push左節點。
疊代解法：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null)
return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
res.add(current.val);
if (current.right != null)
stack.push(current.right); //先push right node
if (current.left != null)
stack.push(current.left);
}
return res;
}
}
核心是先push right，然後處理所有的left結點。如果要與中序後序統一模闆，可以改成下面的代碼：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null)
return res;
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
if (current != null) {
res.add(current.val); // root
stack.push(current);
current = current.left; // left
}
else {
current = stack.pop(); // right
current = current.right;
}
}
return res;
}
}
也可以作出改進，使得隻需要push right結點。
class Solution {
// 隻push right結點的方法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null)
return res;
TreeNode current = root;
while (true)
if (current != null) {
res.add(current.val);
if (current.right != null)
stack.push(current.right);
current = current.left;
}
else if (stack.isEmpty())
return res;
else
current = stack.pop();
}
}
② 二叉樹的中序周遊 LeetCode 94
描述： RT。題目連結
遞歸解法：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(list, root);
return list;
}
public void inOrder(List<Integer> list, TreeNode root) {
if (root == null)
return;
inOrder(list, root.left);
list.add(root.val);
inOrder(list, root.right);
}
疊代同樣要用到棧，隻是要先處理所有left結點，然後在後續的出棧中，先把目前的棧頂值加入到結果集中（left和root），然後再周遊right結點，以達到：left -> root -> right的效果。
疊代解法：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null)
return res;
TreeNode current = root;
while (current != null || !stack.isEmpty())
if (current != null) {
stack.push(current); // 把所有left壓棧
current = current.left;
}
else {
current = stack.pop(); // 出棧順序,棧頂順序為:left, root
res.add(current.val); // 添加到結果集
current = current.right; // 把right壓棧
}
return res;
}
}
③ 二叉樹的後序周遊 LeetCode 145
描述: RT。題目連結
遞歸解法：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postOrder(list, root);
return list;
}
public void postOrder(List<Integer> list, TreeNode root) {
if (root == null)
return;
postOrder(list, root.left);
postOrder(list, root.right);
list.add(root.val);
}
}
後序周遊是在LeetCode中，三個周遊中唯一一個難度為hard的題目（當然，前提是不考慮遞歸）。這是因為前序周遊為：root -> left -> right，中序周遊為： left -> root -> right，而在壓棧過程中，實際上我們第一個壓棧的元素永遠是root，也就是第一個根節點。而後續的操作中，我們可以先處理root，然後按照right，left的順序壓棧，以達到前序周遊的目的。又或者是先處理left，然後出棧的時候處理完left再處理root，最後處理right，達到中序周遊的效果。但是後序周遊有一個很特别的點，它的順序是： left -> right -> root，也就是說我們要最後處理root，這與前面兩種都不相同。然後發現大部分的解法都比較tricky，先進行前序周遊，然後再更換順序，把它變成後序周遊。前序周遊是先push right結點，這裡更改為先push left結點，這樣結果就是：root -> right -> left，然後再完全倒序，就變成了：left -> right -> root
tricky的疊代解法：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null)
return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
res.add(0, current.val); // addFirst, 使得最後的結果就是完全倒序
if (current.left != null)
stack.push(current.left); // 先push left
if (current.right != null)
stack.push(current.right);
}
return res;
}
}
這顯然不是很好，其實後序的關鍵是，先周遊了left跟right子結點，然後才周遊目前結點，是以設定一個HashSet，記錄已經通路過的結點。然後在擷取棧頂元素的時候（不要直接出棧），先去确認子結點是否已經通路，如果已經通路了，這時候再把棧頂元素出棧，添加到結果集種。如果存在不為null的子結點卻不在HashSet中，那麼此時應該把子結點push到棧中，繼續下一輪的循環。（同樣地，先push right，再push left）
正确的疊代解法：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
Set<TreeNode> set = new HashSet<>(); // visited
if (root == null)
return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.peek();
boolean canVisited = true;
// 先push right, 使得出棧優先是left, 達到 left -> right的效果
if (current.right != null && !set.contains(current.right)) {
canVisited = false;
stack.push(current.right);
}
if (current.left != null && !set.contains(current.left)) {
canVisited = false;
stack.push(current.left);
}
// 隻有left跟right都通路了,此時才通路root
if (canVisited) {
res.add(current.val);
set.add(current);
stack.pop(); // 通路了才出棧
}
}
return res;
}
}
④ 二叉樹的層序周遊 LeetCode 102
描述：給你一個二叉樹，請你傳回其按 層序周遊 得到的節點值。 （即逐層地，從左到右通路所有節點）。 題目連結
遞歸解法：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
helper(root, res, 0);
return res;
}
public void helper(TreeNode root, List<List<Integer>> res, int level) {
if (root == null)
return;
if (res.size() == level)
res.add(new ArrayList<>());
res.get(level).add(root.val);
helper(root.left, res, level + 1);
helper(root.right, res, level + 1);
}
}
對于疊代，同樣也會用到棧或者隊列來存儲結點資料。因為是目前層，是以我們可以逐層周遊，把每一層的結點全部添加到Queue當中，然後記錄size。如果size為0，說明目前層已經為空，循環結束。如果不為0，這時候我們要把Queue裡所有的結點都出列，同時添加到List中，在出列的過程中，我們會添加下一層的結點（目前結點的左節點或者右節點）。因為我們要確定隻把目前層的結點全部出列，而下一層的結點會留在下一次循環（另起一個List），是以要保證後面來的資料不會影響到前面資料的順序，最恰當的資料結構是隊列。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) { // Queue為空,說明下一層沒有任何結點
List<Integer> cur = new ArrayList<>();
int size = queue.size(); // 把Queue裡的目前資料全部出列
while (size > 0) {
TreeNode current = queue.poll();
cur.add(current.val);
if (current.left != null)
queue.add(current.left);
if (current.right != null)
queue.add(current.right);
size--;
}
res.add(cur); // 每一次循環就是周遊了一層
}
return res;
}
}
⑤ 二叉樹的垂序周遊 LeetCode 987
描述：給定二叉樹，按垂序周遊傳回其結點值。
對位于 (X, Y) 的每個結點而言，其左右子結點分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一條垂線從 X = -infinity 移動到 X = +infinity ，每當該垂線與結點接觸時，我們按從上到下的順序報告結點的值（ Y 坐标遞減）。
如果兩個結點位置相同，則首先報告的結點值較小。
按 X 坐标順序傳回非空報告的清單。每個報告都有一個結點值清單。
題目連結
分析：本題表述不夠清楚。對于一個結點，先考慮它的x坐标（垂序），然後再考慮它的y坐标（同一垂線，從上往下輸出），最後如果坐标相同（x，y都相同），再根據val的大小來輸出。(這種周遊方式并不常見，也不實用，記住就好，前面4種的應用都很廣泛)
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
Map<TreeNode, int[]> positions = new HashMap<>();
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
positions.put(root, new int[] {0, 0});
int min = 0; // 記錄最左和最右
int max = 0;
while (!queue.isEmpty()) { // 層序周遊, 記錄每個端點的坐标
int size = queue.size();
while (size > 0) {
TreeNode current = queue.poll();
int[] pos = positions.get(current);
if (current.left != null) {
queue.add(current.left);
positions.put(current.left, new int[] {pos[0] - 1, pos[1] + 1});
min = min <= pos[0] - 1 ? min : pos[0] - 1;
}
if (current.right != null) {
queue.add(current.right);
positions.put(current.right, new int[] {pos[0] + 1, pos[1] + 1});
max = max >= pos[0] + 1 ? max : pos[0] + 1;
}
size--;
}
}
int length = max - min + 1;
for (int i = 0; i < length; i++)
res.add(new ArrayList<>());
List<int[]> list = new ArrayList<>(); // 改為使用三維數組存儲{x, y, val}
for (Map.Entry<TreeNode, int[]> entry: positions.entrySet()) {
int[] value = entry.getValue();
int[] tmp = new int[] {value[0], value[1], entry.getKey().val};
list.add(tmp);
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int x = o1[0] - o2[0];
if (x != 0)
return x;
int y = o1[1] - o2[1];
if (y != 0)
return y;
return o1[2] - o2[2]; // x, y, val
}
});
for (int[] ints: list) {
List<Integer> currentList = res.get(ints[0] - min);
currentList.add(ints[2]);
res.set(ints[0] - min, currentList);
}
return res;
}
}
五. 根據兩種周遊來還原樹的結構
①前序 + 中序 LeetCode 105
主要思路：先從前序周遊中得知根結點，然後把根節點代入到中序周遊，把樹劃分成左子樹和右子樹，對子樹進行遞歸，直到每一個子樹都隻有1個結點。直接看圖操作：
之後繼續對子樹進行遞歸，左子樹[9]已經無須繼續操作，是以隻需考慮右子樹了。對右子樹處理完畢之後，遞歸結束，也就得到了最後的結果。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0)
return null;
int rootVal = preorder[0];
int i;
for (i = 0; i < inorder.length; i++)
if (inorder[i] == rootVal)
break;
TreeNode root = new TreeNode(rootVal);
int[] leftInorder = Arrays.copyOfRange(inorder, 0, i);
int[] rightInorder = Arrays.copyOfRange(inorder, i + 1, inorder.length);
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftPreorder.length, preorder.length);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}
這裡的代碼是比較偷懶的複制數組，實際上這會導緻一定的時間開銷。更好辦法是，建立一個helper方法，傳參增加起始的index。但主要的思路都是一樣的。同時有一個細節，不要忘了去掉根節點，它在下一層循環裡并不需要用到（我們隻需要處理子樹）。
② 後序 + 中序 LeetCode 106
主要思路：思路與上面一緻，隻是尋找根節點的方法改為了通過後序周遊。後序周遊的最後一個結點為根節點。後續的操作都一樣，直接看圖操作：
直接也是同樣地遞歸，直到結束，就是最後的結果：
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0)
return null;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
int index = 0;
for (index = 0; index < inorder.length; index++)
if (inorder[index] == postorder[postorder.length - 1])
break;
int[] inorder1 = new int[index];
int[] inorder2 = new int[inorder.length - index - 1];
System.arraycopy(inorder, 0, inorder1, 0, index);
System.arraycopy(inorder, index + 1, inorder2, 0, inorder.length - index - 1);
int[] postorder1 = new int[index];
int[] postorder2 = new int[inorder.length - index - 1];
System.arraycopy(postorder, 0, postorder1, 0, index);
System.arraycopy(postorder, index, postorder2, 0, inorder.length - index - 1);
root.left = buildTree(inorder1, postorder1);
root.right = buildTree(inorder2, postorder2);
return root;
}
}
代碼同樣地，也直接複制數組了，優化方法同上，不再贅述。
六. 左葉子之和
描述： 計算給定二叉樹的所有左葉子之和。LeetCode 404. 題目連結
分析：求和等問題也是直接遞歸就能解決，關鍵是明白什麼是左葉子：必須是某一個結點的左子結點，同時它還是一個葉子，是以遞歸的時候自然而然是有3個判定條件的。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null)
return 0;
if (root.left != null && root.left.left == null && root.left.right == null)
return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}
七. 路徑和
① 路徑總和 LeetCode 112.
描述：給定一個二叉樹和一個目标和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目标和。
分析：一開始看錯題目了，以為任意路徑都可以，然後才發現一定要以“葉子結點"結束，是以要判斷目前是否為葉子。用遞歸的解法也很顯然，如果不為葉子，減去root的值，然後遞歸。
遞歸解法：
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
if (root.left == null && root.right == null)
return root.val == sum;
return hasPathSum(root.left, sum - root.val) ||
hasPathSum(root.right, sum - root.val);
}
}
這道題的疊代解法，需要開辟另一個棧來存儲目前和的結果（不能直接用一個普通變量，因為存在不同的路徑，比如出棧左子節點和右子節點時，要分别考慮）。
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
LinkedList<TreeNode> node_stack = new LinkedList<>();
LinkedList<Integer> sum_stack = new LinkedList<>();
node_stack.push(root);
sum_stack.push(sum - root.val); // 每次node_stack pop,sum_stack減去該val
TreeNode current;
int currentSum;
while (!node_stack.isEmpty()) {
current = node_stack.pop();
currentSum = sum_stack.pop();
if (current.right == null && current.left == null && currentSum == 0)
return true; // 如果pop出來的是葉子,且sum變成0,說明是正确的路徑
if (current.right != null) {
node_stack.push(current.right);
sum_stack.push(currentSum - current.right.val);
}
if (current.left != null) {
node_stack.push(current.left);
sum_stack.push(currentSum - current.left.val);
}
}
return false;
}
}
② 路徑總和 Ⅱ LeetCode 113.
描述：給定一個二叉樹和一個目标和，找到所有從根節點到葉子節點路徑總和等于給定目标和的路徑。
分析：像這種尋找所有路徑的題目，很容易想到回溯算法，也就是DFS。在到終點的時候（葉子結點），判斷是否符合結果（路徑和是否為sum），如果是，添加到結果集。不管如何，後面都是傳回上一層，也就是回溯，然後進行最關鍵的“狀态reset”，也就是把上一個添加到list的值給去掉，也就是回溯的思路。
以本題基本測試用例 [5,4,8,11,null,13,4,7,2,null,null,5,1] 為例畫出回溯過程：
可以先寫出這題最基本的回溯模闆：
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if (root == null)
return res;
helper(root, sum, 0, res, list); // call the backtrack function
return res;
}
public void helper(TreeNode root, int sum, int current,
List<List<Integer> res, List<Integer> list) {
if (.....) {
res.add(new ArrayList<>(list));
return; // backtrack
}
// while or for or if ...
}
}
回溯的條件自然是到了葉子結點，此時判斷是否為有效的路徑，如果是，添加到結果集。回溯之後要把狀态reset，是以後續都有
list.remove(list.size() - 1)
的操作。因為這裡就是普通的前序周遊，是以也不需要while循環，直接if就可以解決了。
代碼：
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if (root == null)
return res;
list.add(root.val);
helper(root, sum, root.val, res, list); // root.val必須要有
return res;
}
public void helper(TreeNode root, int sum, int current,
List<List<Integer>> res, List<Integer> list) {
if (root.left == null && root.right == null && current == sum) {
res.add(new ArrayList<>(list));
return; // 回溯
}
if (root.left != null) {
list.add(root.left.val);
helper(root.left, sum, current + root.left.val, res, list);
list.remove(list.size() - 1);
}
if (root.right != null) {
list.add(root.right.val);
helper(root.right, sum, current + root.right.val, res, list);
list.remove(list.size() - 1);
}
}
}
③ 路徑總和 Ⅲ LeetCode 437.
描述：給定一個二叉樹，它的每個結點都存放着一個整數值。
找出路徑和等于給定數值的路徑總數。
路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（隻能從父節點到子節點）。
二叉樹不超過1000個節點，且節點數值範圍是 [-1000000,1000000] 的整數。
分析：一開始覺得隻是上一題的變種，做了一下才發現難多了，而這題竟然定義為Easy。我一開始是用背包問題的思維，目前root節點是否拿，分為拿和不拿，然後再分别遞歸到左子樹和右子樹。這時候的關鍵代碼大概是：
return helper(root.left, sum, cur + root.val) + helper(root.left, sum, cur) + helper(root.right, sum, cur + root.val) + helper(root.right, sum, cur)
毀掉這段代碼的倒也跟上一題的測試用例一樣，“0”。當一個結點的值為0，或者sum為0，這時候這個代碼就很多錯誤。可能會重複計算，也可能會少計算。後來還是要額外增加一個資料結構，也就是HashMap，用于記錄到達目前元素的路徑上，之前的所有元素的和（根節點到目前元素）。直覺上會覺得，該題路徑不要求從根結點開始。但假設路徑的起始結點為node1，它具有父節點node2，node2有父節點node3，結束結點為node0。
這時候應該是：node0 - node1 == sum
但我們記錄的是：
f (node0) = node0 + node2 + node3
f (node1) = node1 + node2 + node3
是以： f(node0) - f(node1) = = node0 - node1 == sum
即結果是一樣的。這個概念正式地稱為 字首和。值得注意的是，因為DFS實際上也是回溯的過程，那麼回溯的時候也是要進行狀态reset的，否則後面的結點在回溯的時候會影響前面的狀态。
代碼：
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null)
return 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return helper(root, sum, 0, map);
}
public int helper(TreeNode root, int sum, int prev, Map<Integer, Integer> map) {
if (root == null)
return 0;
int res = 0;
prev += root.val;
res += map.getOrDefault(prev - sum, 0);
// 目前和為prev,尋找前面和為prev - sum的,內插補點就是sum(從後往前推)
map.put(prev, map.getOrDefault(prev, 0) + 1); // 目前節點的字首和
res += helper(root.left, sum, prev, map);
res += helper(root.right, sum, prev, map); // 下一層
map.put(prev, map.get(prev) - 1); // 回溯, 狀态reset
return res;
}
}
八. 二叉搜尋樹BST
二叉搜尋樹又稱BST，其特點為左子樹的元素都小于根結點，右子樹的元素都大于根節點。這是不考慮重複元素的情況，如果考慮，可以規定相同的元素往左子樹放，或者右子樹放，但此時複雜性還是增加不少，對于查詢的時候可能需要分别遞歸查找兩個子樹，是以一般考慮無重複元素的BST即可。
① 修剪二叉搜尋樹 LeetCode 669.
描述：給定一個二叉搜尋樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜尋樹，使得所有節點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節點，是以結果應當傳回修剪好的二叉搜尋樹的新的根節點。
分析：做樹的題目一定要記住，先考慮遞歸，再考慮其他的。因為樹的結構很複雜，如果你直接把問題整體地考慮，很難有思路。比如這一題，你可能需要改變根結點，那麼修剪之後剩下哪些結點？哪個結點應該作為根節點？如果先得出剩餘的結點，然後再手動構造BST，這個顯然不是一個好辦法。是以就要把問題細化，也就是回歸遞歸的三個步驟。(為什麼突然又要拿出“三大步驟”來做題？因為上一題把我卡了好久= =)
-
遞歸什麼時候結束？
顯然，root為null就結束，這時候就直接傳回null
-
應該傳回什麼？
同樣地，每一層的傳回值都是相同的，既然第一層傳回的是根結點，是以每一層傳回的都是根節點
-
每一層遞歸應該做什麼？
既然要考慮的是根節點，是以自然就是先判斷根節點與L,R的關系比較。如果root的值小于L，那麼root就要去掉，此時最恰當的是傳回比root大一點的結點，也就是root.right。大于R同理。如果root.right仍然不符合怎麼辦？同樣地，這是下一層遞歸要考慮的，我們在目前層不需要考慮。那麼在處理完root之後是否就結束了呢？并不，此時隻是說明這個root不需要改變了，這時候還要遞歸地考慮root的左子樹和右子樹的值，它們有可能不屬于[L, R]範圍。處理方法也是同樣地，一層一層循序漸進，是以考慮的是root.left, root.right
代碼：
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null)
return null;
// 傳回右子樹, 因為right >= root,如果仍然不符合,繼續遞歸
if (root.val < L)
return trimBST(root.right, L, R);
if (root.val > R)
return trimBST(root.left, L, R); // 同上
// 處理子結點 (root滿足了,遞歸去除子樹不符合的值)
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
② 二叉搜尋樹中第K小的元素 LeetCode 230.
描述：給定一個二叉搜尋樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明：
你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜尋樹元素個數。
分析：對BST進行中序周遊，将得到一個有序的線性表，因而再擷取第K小的元素就很簡單。
class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inOrder(root, list, k);
return list.get(k - 1);
}
public void inOrder(TreeNode root, List<Integer> list, int k) {
if (root == null || list.size() == k)
return;
inOrder(root.left, list, k);
list.add(root.val);
inOrder(root.right, list, k);
}
}
看了一下排名最高的解法，其實也是中序周遊，隻是用了全局變量提升了效率而已：
class Solution {
int res = 0;
int k = 0;
public int kthSmallest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if (root == null)
return;
dfs(root.left);
k--;
if(k == 0)
res = root.val;
dfs(root.right);
}
}
進階： 如果二叉搜尋樹經常被修改（插入/删除操作）并且你需要頻繁地查找第 k 小的值，你将如何優化
kthSmallest
函數？
這時候可以維護一個大小為k的堆。如果要擷取第k小，那麼就維護最大堆，此時堆頂元素就是第k小。一次維護的時間複雜度為O(logN)，效率很高。
③ 把二叉搜尋樹轉換成累加樹 LeetCode 538.
描述：給定一個二叉搜尋樹（Binary Search Tree），把它轉換成為累加樹（Greater Tree)，使得每個節點的值是原來的節點值加上所有大于它的節點值之和。
分析：如果願意，仍然可以直接中序周遊，然後再對List進行累加。但其實這道題需要的是從右往左添加（最右的元素不需要操作，倒數第二右的元素隻需要添加最右元素，以此類推）。是以可以把周遊順序改成：right -> root -> left，使用一個全局變量記錄右邊的元素值。
代碼：
class Solution {
int right = 0;
public TreeNode convertBST(TreeNode root) {
inOrder(root);
return root;
}
public void inOrder(TreeNode root) {
if (root == null)
return;
inOrder(root.right);
root.val += right; // 加上右邊的元素
right = root.val; // right更新為現在的root.val
inOrder(root.left);
}
}
因為這個遞歸的方法隻有一個參數，讓人很難去嘗試直接去掉，遞歸convertBST方法本身，于是可以化簡代碼：
class Solution {
int right = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
root.val += right;
right = root.val;
convertBST(root.left);
}
return root;
}
}
④ 二叉搜尋樹的最近公共祖先 LeetCode 235
描述：給定一個二叉搜尋樹, 找到該樹中兩個指定節點的最近公共祖先。“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。” 題目連結
分析：可以一直遞歸，直到找到最近的公共祖先，但是這就浪費了BST的條件，是以直接疊代就可以了。根節點root肯定是二者的公共祖先，疊代逐漸找到最近的公共祖先。這時候root與p，q的大小隻有四種可能：root介于二者之間，root比二者都大，root比二者都小，與二者之一相等。對于第一種情況，此時root是公共祖先，因而root.left跟root.right都不會是公共祖先了（root位于p，q中間，而root是從根節點開始疊代的）。對于第二種情況，p，q都位于root的左子樹，是以直接：
root = root.left
即可找到更近的公共祖先，第三種情況同理。第四種情況，顯然也是直接傳回（root與其中之一相等，且是它們兩個的公共祖先，那自然是最近的公共祖先了）
代碼：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != p && root != q) {
if ((p.val < root.val && q.val > root.val) ||
(q.val < root.val && p.val > root.val))
return root;
// 如果root是公共祖先, 那麼root.left跟root.right都不會是公共祖先(root是p,q中間)
else if (p.val < root.val) //p, q < root
root = root.left;
else
root = root.right; // p, q > root
}
return root;
}
}
⑤ 二叉樹的最近公共祖先 LCA問題 LeetCode 236
描述：與上一題相同，隻是這一題是普通的二叉樹，而不是BST。題目連結
分析：可以建立一個判定是否為子結點的方法，然後對root進行遞歸。這樣顯然就進行了兩次O(n ^ 2)的循環，是以效率非常低。并不推薦。這時候我們再次拿出遞歸三步驟來進行解題：
-
遞歸什麼時候結束？
當root為null的時候，或者等于p或q二者之一。（其實就是問邊界情況，但遞歸就是有了這個邊界才不會無限循環下去）
-
應該傳回什麼？
既然是調用自身，是以同樣地，傳回以目前root為根節點的樹，對于結點p，q的最近公共祖先
-
每一層遞歸應該做什麼？
判斷root是否為LCA，如果是，直接傳回，如果不是，繼續遞歸左子樹和右子樹。其實每一次遞歸都隻有4種可能：null（已經到達邊界），p/q（如果root等于二者之一，同樣也可以直接傳回），root.left，root.right.顯然，當
root == null || root == p || root == q
① root.left，root.right的傳回值都不為null。說明目前的root就是LCA （就像BST的if情況）
② root.left的傳回值為null，root.right傳回值不為null。顯然LCA在右子樹，直接傳回root.right的傳回值
③root.left不為null，root.right為null。同上。
④二者都為null。return null。實際上不會到達，是以情況3和4直接寫成else也是可以的。
代碼：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null)
return root; // left最後遞歸到p, right遞歸到q,即分别在兩側, 自然目前root就是LCA
else if (left != null)
return left;
else
return right;
}
}