今日任务：

1. LeetCode39 组合总和
2. LeetCode40 组合总和 Ⅱ
3. LeetCode131 分割回文串



资料来源：

1. [代码随想录 | LeetCode39 组合总和]()
2. [代码随想录 | LeetCode40 组合总和 Ⅱ]()
3. [代码随想录 | LeetCode131 分割回文串]()

### 1 LeetCode39 组合总和

:::info{title="题目"}
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

 

示例 1：
```
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
```
示例 2：
```
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
```
示例 3：
```
输入: candidates = [2], target = 1
输出: []
```

提示：

- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
:::

回溯秒了。这题是无重复元素，同时说明可以无限制地挑选元素，那在递归到下一层的时候，仍然将当前元素选上就可以了。

:::tip{title="提示"}
start_index，这样的变量用来指示每一层的递归从哪里开始。一般情况下，**如果是从单个集合中取元素组成组合/排列，那么是要用start_index来指示下一层递归的循环从哪里开始**；如果是从多个集合中取元素组成组合的话，因为每个元素都是从0开始循环，所以可以不用start_index来记录循环应该从哪里开始。

注意这个start_index是记录循环从哪里开始的，而上一个电话号码的题不需要这个记录。之所以上一题的写法中也有index，是因为它记录的是数字长度（即递归深度）。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.candidates = []
        self.target = 0
        self.path = []
        self.result = []

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.target = target
        self.candidates = candidates
        self.recursion(0)
        return self.result

    def recursion(self, index):
        if sum(self.path) == self.target:
            self.result.append(self.path.copy())
        if sum(self.path) > self.target:
            return
        for i in range(index, len(self.candidates)):
            self.path.append(self.candidates[i])
            self.recursion(i)  # 递归到下一层时 不要+1 这样下一层循环开始时仍然会加这个元素
            self.path.pop()
```        

另外，这题可以通过对给定的数组进行排序来合理剪枝。

### 2 LeetCode40 组合总和 Ⅱ

:::info{title="题目"}
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

 

示例 1:
```
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```
示例 2:
```
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
```

提示:

- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
:::

和上一个题的区别在于，给定的数组不是无重复的了，而且要求每个元素只能取一次，因此需要在树层上进行去重。

:::tip{title="提示"}
关于回溯中的去重，一共有三种：树枝去重、树层去重和递归去重。

以本题为例，如果candidates为[1, 1, 2]，那么回溯形成的树是这样的：

![4efc6caaf18530245c83c5dc6c0b99b.jpg](https://www.misaka19327.cc/static/img/fd6a3a7a31dc0faa1eb756b6e9ee4bf2.4efc6caaf18530245c83c5dc6c0b99b.jpg)

在这题的语境下，如果要用树层查重，那么题目要求应该是“解集不能包含重复的组合”；如果要用树枝查重，那么题目就应该要求“解集中的组合中不能包含重复的元素”。总的来说，如果是只对单个结果内的元素进行查重，就要考虑树枝查重；如果是对所有结果进行查重，就要考虑树层查重。

树枝查重常用的方法是定义一个和题目给定数组长度相同的数组index_used，每次向path数组中添加元素时，先检查该元素在题目给定数组的下标在index_used的位置是否为0。如果不为0，则说明该元素已经被使用过，直接跳过该元素；如果为0，则说明该元素还没有被使用过，照常添加元素的同时将index_used对应位置置1。在递归回来的时候，还需要将对应位置置0。

树层查重常用的方法是先对题目给定的数组进行排序，然后每次循环的时候从第二个元素开始检查，是否和上一个元素相同，相同就跳过该元素。

还有一种比较特殊的查重是针对单次递归的查重，例子就是491 递增子序列，需要特殊分析。它需要根据题目给定数组中元素可能值设置哈希数组num_used，每次向path中添加元素时，需要在num_used中进行检查。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.candidates = []
        self.target = 0
        self.path = []
        self.result = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.target = target
        candidates.sort()
        self.candidates = candidates
        self.recursion(0)
        return self.result

    def recursion(self, index):
        if sum(self.path) == self.target:
            self.result.append(self.path.copy())
        if sum(self.path) > self.target:
            return
        for i in range(index, len(self.candidates)):
            if i != index:
                if self.candidates[i] == self.candidates[i - 1]:
                    continue
            self.path.append(self.candidates[i])
            self.recursion(i + 1)
            self.path.pop()
```            

### 3 LeetCode131 分割回文串

:::info{title="题目"}
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 
回文串
 。返回 s 所有可能的分割方案。

 

示例 1：
```
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
```
示例 2：
```
输入：s = "a"
输出：[["a"]]
```

提示：

- 1 <= s.length <= 16
- s 仅由小写英文字母组成
:::

回溯秒了。这道题如果能看出怎么回溯的话就不难，难的就是怎么把它和回溯的思考过程匹配上。组合和排列问题很好匹配，递归的深度就是一次组合/排列的过程，循环的长度就是在已经确定的部分下的其他所有可能性。而切割问题也是可以依照这个思路去思考的。

![f837e1852502359b7130b2fcd3637df.jpg](https://www.misaka19327.cc/static/img/680123a5985639dd795b742615f0120f.f837e1852502359b7130b2fcd3637df.jpg)

判断是否为回文串，双指针就好。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.s = ""
        self.result = []

    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        self.back_tracking(0)
        return self.result

    def is_palindrome(self, s: str) -> bool:
        forward_index, last_index = 0, len(s) - 1
        while forward_index <= last_index:
            if s[forward_index] != s[last_index]:
                return False
            forward_index += 1
            last_index -= 1
        return True

    def back_tracking(self, index: int):
        if index == len(self.s):
            self.result.append(self.path.copy())
        temp = ""
        for i in range(index, len(self.s)):
            temp += self.s[i]
            if self.is_palindrome(temp):
                self.path.append(temp)
                self.back_tracking(i + 1)
                self.path.pop()
```

代码随想录算法训练营第二十七天 | LeetCode39 组合总和、LeetCode40 组合总和 Ⅱ、LeetCode131 分割回文串

今日任务：

1. LeetCode216 组合总和Ⅲ
2. LeetCode17 电话号码的字母组合



资料来源：

1. [代码随想录 | LeetCode216 组合总和Ⅲ](https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html)
2. [代码随想录 | LeetCode17 电话号码的字母组合](https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html)

### 1 LeetCode216 组合总和Ⅲ

:::info{title="题目"}
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

 

示例 1:
```
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
```
示例 2:
```
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
```
示例 3:
```
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
```

提示:

- 2 <= k <= 9
- 1 <= n <= 60
:::

回溯秒了。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.target_sum = 0
        self.target_length = 0
        self.result = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        for i in range(num_added + 1, 10):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return
```       

和昨天的题一样，可以剪枝。

``` python
# 剪枝版本
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def __init__(self):
        self.path = []
        self.target_sum = 0
        self.target_length = 0
        self.result = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if len(self.path) > self.target_length:
            return
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        # 剪枝 1 目前已经有多长 len(self.path)
        # 2 目前还需要多长 self.target_length - len(self.path)
        # 3 所以循环到什么位置 range(num_added + 1, 10 - (self.target_length - len(self.path)))
        for i in range(num_added + 1, 10 - (self.target_length - len(self.path)) + 1):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return
```        

### 2 LeetCode17 电话号码的字母组合

:::info{title="题目"}
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
```
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
```
示例 2：
```
输入：digits = ""
输出：[]
```
示例 3：
```
输入：digits = "2"
输出：["a","b","c"]
```

提示：

- 0 <= digits.length <= 4
- digits[i] 是范围 ['2', '9'] 的一个数字。
:::

回溯一样秒。先建立数字到字符串的映射（可以优化为数组），按传入的字符串长度决定递归深度，每个数字对应的字母数量决定for次数，最后递归回来记得回溯就行。

:::tip{title="提示"}
python做传列表参数或者两个列表互相append的时候如果出问题，优先考虑要不要copy。
:::

``` python
from typing import List

class Solution:
    def __init__(self):
        self.map = {2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
        self.path = []
        self.result = []
        self.digits = []

    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        self.digits = list(digits)
        self.recursion(0)
        result_ = []
        for i in self.result:
            result_.append("".join(i))
        return result_

    def recursion(self, index: int):
        if index == len(self.digits):
            self.result.append(self.path.copy())
            return
        chars = self.map.get(int(self.digits[index]))
        for i in chars:
            self.path.append(i)
            self.recursion(index + 1)
            self.path.pop()
```

代码随想录算法训练营第二十五天 | LeetCode216 组合总和Ⅲ、LeetCode17 电话号码的字母组合

路由与交换技术 记录2

今日任务：

1. 回溯理论基础
2. LeetCode77 组合



资料来源

1. [代码随想录 | 回溯理论基础](https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
2. [代码随想录 | LeetCode77 组合](https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html)

### 1 回溯理论基础

回溯法，也叫回溯搜索法，是一种用于搜索符合条件的情况的使用递归的通用算法思路。它的本质就是暴力搜索，因此它的效率并不高，但是有些问题是本来就没有什么有效的算法，能出结果就算成功，回溯属于是矬子里拔大个，能提升它的效率的方法只有进行适当的剪枝操作。回溯算法能解决的问题如下：

1. 组合问题：n个数字中，找出符合一定规则的k个数字的组合。
2. 切割问题：一个字符串中，按一定的规则能够有多少切法。
3. 子集问题：n个数字中，找出符合一定规则的子集。
4. 排列问题：n个数字中，按一定规则进行排列，有多少种排列方式。
5. 棋盘问题：N皇后问题，数独问题。

:::tip{title="提示"}
组合问题和排列问题的区别在于，组合问题的答案不关注元素的顺序，排列问题的答案关注元素的顺序。同为[1, 2]，[2, 1]，组合问题认为这就是一个答案，排列问题认为这是两种答案。
:::

因为回溯问题都是用递归来解决的，所有所有回溯问题都可以被抽象为树形结构，要查找的集合的大小就构成了树的宽度，递归的深度就构成了树的深度。有递归就要有终止条件，所以这棵树必然是一棵高度有限的n叉树。

相比递归问题的三要素，回溯问题的模板就多了一个回溯的过程：

``` 
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
```

### 2 LeetCode77 组合

:::info{title="题目"}
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

 

示例 1：
```
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```
示例 2：
```
输入：n = 1, k = 1
输出：[[1]]
```

提示：

- 1 <= n <= 20
- 1 <= k <= n
:::

这道题就是经典的暴力行不通只能回溯的情况。如果是要暴力循环去做的话，for循环的层数必须要与k相同，这就不可能行得通。而回溯可以通过在递归中进行循环的方式来做。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        self.back_tracking(n, k, 1)
        return self.result

    def back_tracking(self, n: int, k: int, start_index: int):
        if len(self.path) == k:  # 满足条件 终止递归
            self.result.append(self.path.copy())
            return
        for i in range(start_index, n + 1):  # 单层递归的逻辑
            self.path.append(i)
            self.back_tracking(n, k, i + 1)
            self.path.pop()
        return
```        

这道题也可以进行适当的剪枝操作。一种情况是k为1的时候，那就没什么必要再去递归了，直接生成结果就行了。另外还有k足够大的时候，有些递归的情况里，递归到最后result都不够长，因此注定不会有结果。这部分也可以进行剪枝。剪枝后的代码如下：

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 1:
            return [[i] for i in list(range(1, n + 1))]
        self.back_tracking(n, k, 1)
        return self.result

    def back_tracking(self, n: int, k: int, start_index: int):
        if len(self.path) == k:  # 满足条件 终止递归
            self.result.append(self.path.copy())
            return
        for i in range(start_index, (n + 1) - (k - len(self.path)) + 1):  # 剪枝操作
            self.path.append(i)
            self.back_tracking(n, k, i + 1)
            self.path.pop()
        return
```

剪枝思路：

1. 当前递归中，已经进去的元素有`len(self.path)`个。
2. 还需要`k - len(self.path)`个。
3. 在集合中，遍历终点是`(n + 1) - (k - len(self.path)) + 1)`，如果超过这个终点在继续遍历下去，之后递归到底时的path都不会够k个元素。

代码随想录算法训练营第二十四天 | LeetCode77 组合

今日任务：

1. LeetCode669 修剪二叉树
2. LeetCode108 将有序数组转换为二叉搜索树
3. LeetCode538 将二叉搜索树转换为累加树
4. 二叉树部分总结



资料来源：

1. [代码随想录 | LeetCode669 修剪二叉树](https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode108 将有序数组转换为二叉搜索树](https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | LeetCode538 将二叉搜索树转换为累加树](https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | 二叉树总结篇](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html)

### 1 LeetCode669 修剪二叉树

:::info{title="题目"}
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
```
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
```
示例 2：
```
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
```

提示：

- 树中节点数在范围 [1, 104] 内
- 0 <= Node.val <= 104
- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
- 0 <= low <= high <= 104
:::

剪枝剪了半天也没剪明白，直接看了代码随想录。递归写法还是按递归三要素走的，如果到了空节点就停止递归。单层递归里，如果当前处理的节点不符合条件，就往可能符合条件的子树里去找：大于high就往左子树递归，小于low就往右子树递归，直接返回递归的结果，当前处理的不符合条件节点就没了；如果当前处理的节点符合条件，那就往左右子树去递归，返回当前节点就好。

``` python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        return self.recursion(root, low, high)

    def recursion(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None:  # 终止条件
            return None
        # 单层递归的逻辑
        # 当前节点不符合条件的话就处理
        if root.val < low:
            return self.recursion(root.right, low, high)  # 返回的是子树的查找结果 接住结果的是当前节点的上一层节点 当前这个不符合条件的节点就删掉了
        if root.val > high:
            return self.recursion(root.left, low, high)
        # 如果当前节点符合条件
        root.left = self.recursion(root.left, low, high)
        root.right = self.recursion(root.right, low, high)
        return root
```        

还有一个迭代版本，说实话挺不好想的，也挺不好写的。

``` python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        # 先将root移动到区间里
        while root is not None and (root.val > high or root.val < low):
            if root.val > high:
                root = root.left
            else:
                root = root.right

        # 移动完了 处理左右子树
        pointer = root
        while pointer is not None:
            while pointer.left is not None and pointer.left.val < low:  # pointer.left不符合条件
                pointer.left = pointer.left.right  # 将左子树的右子树接过来 接着循环判断
            pointer = pointer.left

        pointer = root
        while pointer is not None:
            while pointer.right is not None and pointer.right.val > high:
                pointer.right = pointer.right.left
            pointer = pointer.right

        return root
```        

### 2 LeetCode108 将有序数组转换为二叉搜索树

:::info{title="题目"}
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 
平衡
 二叉搜索树。
 
示例 1：
```
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
```
示例 2：
```
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
```

提示：

- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 按 严格递增 顺序排列
:::

这道题的思路和前几天做过的一道题思路特别像。平衡二叉树么，要求子树高度差不能超过1，那我创建两个子树的时候平分目前有的节点不就行了，这就是这道题的整体思路。

``` python
from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.nums = None

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            return TreeNode(val=nums[0])
        self.nums = nums
        return self.recursion(len(nums) - 1, 0)

    def recursion(self, high: int, low: int) -> Optional[TreeNode]:
        if high < low:
            return None
        root = int((high + low) / 2)
        root_node = TreeNode(val=self.nums[root])
        root_node.right = self.recursion(high, root + 1)
        root_node.left = self.recursion(root - 1, low)
        return root_node
```        

### 3 LeetCode538 将二叉搜索树转换为累加树

:::info{title="题目"}
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：
```
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
```
示例 2：
```
输入：root = [0,null,1]
输出：[1,null,1]
```
示例 3：
```
输入：root = [1,0,2]
输出：[3,3,2]
```
示例 4：
```
输入：root = [3,2,4,1]
输出：[7,9,4,10]
```

提示：

- 树中的节点数介于 0 和 104 之间。
- 每个节点的值介于 -104 和 104 之间。
- 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
:::

反向中序秒了。

``` python
from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        stack = deque()
        node = root
        stack.append(node)
        sum = 0
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                sum += node.val
                node.val = sum
            else:
                if node.left is not None:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
        return root
```    

### 4 二叉树部分总结

嫖张图过来吧，别的感觉好像也没什么可以总结的了。个人觉得比较重要的点如下，之后二刷还有的话再补充：

1. 统一写法风格的前中后序遍历二叉树，那个记下来之后用起来真的很方便。
2. 对搜索二叉树，就把它看成一个有序数组去想，在不少的场合能够加速思考过程。反正对它中序遍历就是有序数组了。
3. 如果题目对树的结构要求比较高（或者说节点的位置关系），那么优先考虑递归。
4. 递归三件套：递归函数参数和返回值、终止条件、单层递归顺序。

![image.png](https://www.misaka19327.cc/static/img/4e5e2328e90bcaf572f4687b184fb71d.image.png)