今日任务：

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)

代码随想录算法训练营第二十三天 | LeetCode669 修剪二叉树、LeetCode108 将有序数组转换为二叉搜索树、LeetCode538 将二叉搜索树转换为累加树

今日任务：

1. LeetCode235 二叉搜索树的最近公共祖先
2. LeetCode701 二叉搜索树中的插入操作
3. LeetCode450 删除二叉搜索树中的节点



资料来源：

1. [代码随想录 | LeetCode235 二叉搜索树的最近公共祖先](https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html)
2. [代码随想录 | LeetCode701 二叉搜索树中的插入操作](https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html)
3. [代码随想录 | LeetCode450 删除二叉搜索树中的节点](https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html)

### 1 LeetCode235 二叉搜索树的最近公共祖先

:::info{title="题目"}
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
```
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
```
示例 2:
```
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
```
说明:

- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
:::

这个思路和昨天大致相似，只是这次判断要快很多。如果这次递归的节点和p或者q值相等，那么就认为这个节点就是要找的节点；如果p比当前节点大同时q比当前节点小，那么这个节点也是要找的节点；如果p和q同时比当前节点大/小，就继续往右子树/左子树上找。

``` python
from typing import Optional

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val:  # 递归函数里p是较大的数字
            return self.recursion(root, p, q)
        else:
            return self.recursion(root, q, p)

    def recursion(self, root: TreeNode, p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
        if q.val < root.val < p.val or q.val == root.val or p.val == root.val:
            return root
        elif p.val < root.val and q.val < root.val and root.left is not None:
            return self.recursion(root.left, p, q)
        elif p.val > root.val and q.val > root.val and root.right is not None:
            return self.recursion(root.right, p, q)
```     

### 2 LeetCode701 二叉搜索树中的插入操作

:::info{title="题目"}
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：
```
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
```
示例 2：
```
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
```
示例 3：
```
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
```

提示：

- 树中的节点数将在 [0, 104]的范围内。
- -108 <= Node.val <= 108
- 所有值 Node.val 是 独一无二 的。
- -108 <= val <= 108
- 保证 val 在原始BST中不存在。
:::

看到这个题的时候，有两个想法。一个想法是找到离要插入的节点最近的节点然后进行操作；另一个想法是以要插入的节点为根，重新构建一个树。

我写的代码是根据第一个想法而来的。先按中序找到第一个大于要插入节点的值的节点，之后在它的子树的最右侧插入节点。写完之后发现确实文档说得对，比想象的要简单。

``` 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val=val)
        stack = deque()
        node = root
        stack.append(root)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                if node.val > val:
                    if node.left is None:
                        node.left = TreeNode(val=val)
                    else:
                        node = node.left
                        while node.right is not None:
                            node = node.right
                        node.right = TreeNode(val=val)
                    return root
            else:
                if node.right is not None:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left is not None:
                    stack.append(node.left)
        node = root
        while node.right is not None:
            node = node.right
        node.right = TreeNode(val=val)
        return root
```     

看完文档之后发现我还是想复杂了。**搜索二叉树无论插入什么值，这个值都一定能够在叶子节点上找到一个位置**。那事情就好说了，按照要插入的数值一个劲往叶子节点找就行了，找到空就插入，然后直接返回根节点就行。

``` 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)
        node = root
        pre_node = node
        while node is not None:
            pre_node = node
            if node.val > val:
                node = node.left
            else:
                node = node.right
        if pre_node.val > val:
            pre_node.left = TreeNode(val)
        else:
            pre_node.right = TreeNode(val)
        return root
```        

### 3 LeetCode450 删除二叉树中的节点

:::info{title="题目"}
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

- 首先找到需要删除的节点；
- 如果找到了，删除它。
 

示例 1:
```
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7]。
另一个正确答案是 [5,2,6,null,4,null,7]。
```
示例 2:
```
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
```
示例 3:
```
输入: root = [], key = 0
输出: []
```

提示:

- 节点数的范围 [0, 104].
- -105 <= Node.val <= 105
- 节点值唯一
- root 是合法的二叉搜索树
- -105 <= key <= 105
 

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
:::

第一思路是先找着这个节点和它的父节点，然后这个节点被它的右子树代替，它的左子树就成为右子树的最左边的节点的左子树。

``` 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None
        pointer = root
        pre_pointer = None
        while pointer is not None:  # 先找要删的节点和它的父节点
            if pointer.val == key:
                break
            pre_pointer = pointer
            if pointer.val > key:
                pointer = pointer.left
            else:
                pointer = pointer.right
        if pointer is None:  # 没找着
            return root
        else:
            if pre_pointer is not None:  # 如果要删的不是根节点
                if pointer.right is not None:  # 如果右子树不为空
                    if pre_pointer.left is pointer:  # 接右子树
                        pre_pointer.left = pointer.right
                    elif pre_pointer.right is pointer:
                        pre_pointer.right = pointer.right
                    # 从这开始接左子树
                    temp = pointer.right
                    # 如果右子树不为空 就往右子树的左节点上找 找到空了再接上
                    while temp.left is not None:
                        temp = temp.left
                    temp.left = pointer.left
                else:  # 如果右子树为空 那直接接左子树就好
                    if pre_pointer.left is pointer:  # 接右子树
                        pre_pointer.left = pointer.left
                    elif pre_pointer.right is pointer:
                        pre_pointer.right = pointer.left
                return root
            else:  # 如果要删的是根节点
                root = root.right  # 还是先接右子树 这次是将右子树作为根节点
                if root is not None:  # 上面一样的接法
                    temp = root
                    while temp.left is not None:
                        temp = temp.left
                    temp.left = pointer.left
                    return root
                else:  # 如果右子树为空 那直接返回左子树就行了
                    return pointer.left
```                    

:::tip{title="提示"}
代码随想录里提到了一个比较有趣的删节点的方法，虽然是针对普通二叉树的。

1. 找到要删除的节点和要删除的节点的右子树的最左节点。
2. 找到的这两个节点进行值的交换。
3. 再将那个交换后的节点变成空。

``` cpp
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};
```
:::

代码随想录算法训练营第二十二天 | LeetCode235 二叉搜索树的最近公共祖先、LeetCode701 二叉搜索树中的插入操作、LeetCode450 删除二叉搜索树中的节点

今日任务：

1. LeetCode530 二叉搜索树的最小绝对差
2. LeetCode501 二叉搜索树中的众数
3. LeetCode236 二叉树的最近公共祖先



资料来源：

1. [代码随想录 | LeetCode530 二叉搜索树的最小绝对差](https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode501 二叉搜索树中的众数](https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | LeetCode236 二叉树的最近公共祖先](https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 LeetCode530 二叉搜索树的最小绝对差

:::info{title="题目"}
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：
```
输入：root = [4,2,6,1,3]
输出：1
```
示例 2：
```
输入：root = [1,0,48,null,null,12,49]
输出：1
```

提示：

- 树中节点的数目范围是 [2, 104]
- 0 <= Node.val <= 105
 

注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
:::

一开始想的是层序，因为一开始觉得这个最小绝对差一定出在父子节点之间。后来提交发现不对，二叉搜索树是有可能根节点和左子树的最右叶子的差值是最小的，只能中序。搜索二叉树只有中序出来的是有序数组。

``` 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        # 根据题目条件 必定有差值
        queue = deque()
        pointer1, pointer2 = root, TreeNode(val=0) # pointer2找个最小的 不能指向根节点 自己减自己就到0了 没法再比了
        queue.append(pointer1)
        result = 100000
        while len(queue) != 0:
            pointer1 = queue.pop()
            if pointer1 is None:
                pointer1 = queue.pop()
                if abs(pointer2.val - pointer1.val) < result:
                    result = abs(pointer2.val - pointer1.val)
                pointer2 = pointer1
            else:
                if pointer1.left is not None:
                    queue.append(pointer1.left)
                queue.append(pointer1)
                queue.append(None)
                if pointer1.right is not None:
                    queue.append(pointer1.right)
        return result
```  

``` 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 __init__(self):
        self.result = 100000
        self.previous_root = TreeNode(val=0)

    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        self.recursion(root)
        return self.result

    def recursion(self, root: TreeNode):
        if root is None:
            return
        self.recursion(root.right)
        self.result = min(abs(self.previous_root.val - root.val), self.result)
        self.previous_root = root
        self.recursion(root.left)
```        

### 2 LeetCode501 二叉搜索树中的众数

:::info{title="题目"}
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
 
示例 1：
```
输入：root = [1,null,2,2]
输出：[2]
```
示例 2：
```
输入：root = [0]
输出：[0]
```
提示：

- 树中节点的数目在范围 [1, 104] 内
- -105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
:::

这题学到了很重要的一点，只要是在中序遍历中，对二叉搜索树的操作都可以被视作对一个有序数组的操作。另外，这题对树遍历一次即可，遍历的同时对最大频率和当前频率同时进行更新。如果当前频率大于最大频率，那么更新最大频率并且清空结果数组再将当前的元素添加进去即可。

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

# 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.result = []
    #     self.previous_node = TreeNode(val=None)

    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        stack = deque()
        node = root
        stack.append(node)
        result = []
        previous_val = None
        count = 0
        max_count = 1
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                if previous_val is None:  # 第一次进入比较 初始化
                    count = 1
                    previous_val = node.val
                else:
                    if previous_val == node.val:  # 相同
                        count += 1
                    else:  # 不同 重新初始化
                        previous_val = node.val
                        count = 1
                if count == max_count:  #如果频率达到最大频率就添加元素
                    result.append(node.val)
                elif count > max_count:  # 如果当前元素超过最大频率 就清空数组 更新最大频率 再将当前元素添加进去
                    max_count = count
                    result.clear()
                    result.append(node.val)
            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 result
```   

### 3 LeetCode236 二叉树的最近公共祖先

:::info{title="题目"}
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
```
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
```
示例 2：
```
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
```
示例 3：
```
输入：root = [1,2], p = 1, q = 2
输出：1
```

提示：

- 树中节点数目在范围 [2, 105] 内。
- -109 <= Node.val <= 109
- 所有 Node.val 互不相同 。
- p != q
- p 和 q 均存在于给定的二叉树中。
:::

> 这道题一开始是自己写出来的，但是看过视频讲解之后才意识到，即使自己能想到大体的解法，看过视频还是有收获。

一开始的想法就是回溯，在后序遍历中，如果遇到要查找的节点（题目已经规定这个节点一定存在且值不相同），就回溯一个True。在一次递归中，同时收到的三个bool值：左子树回溯的值，右子树回溯的值，还有这次递归的根节点是否是要查找的节点。如果这三个值中有两个为True，就认为该节点是题目要求的“最近公共祖先”，修改类成员；如果只有一个为True，那么就直接返回True，表示以本次递归节点为根节点的子树中有要查找的节点；如果没有True，就返回False。为了加速，可以每次都检查类成员是否被赋值，如果是则直接跳过。

这题没有迭代解法，我认为原因在于迭代不能很好的保存具体的二叉树的层信息和左右位置信息，而递归栈可以保存下来。如果要使用迭代的话，会非常麻烦。

``` python
# 我的代码
from collections import deque

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

class Solution:
    def __init__(self):
        self.result = None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.recursion(root, p, q)
        return self.result

    def recursion(self, root: TreeNode, p: TreeNode, q: TreeNode) -> bool:
        if self.result is not None:
            return True
        if root is None:
            return False
        left = self.recursion(root.left, p, q)
        right = self.recursion(root.right, p, q)
        if p.val == root.val or q.val == root.val:
            middle = True
        else:
            middle = False
        if [left, right, middle].count(True) == 2 and self.result is None:
            self.result = root
        if True in (middle, left, right):
            return True
        return False
```

实际的解法是直接返回节点。在递归的的过程中，如果当前节点为空，则返回空；如果当前节点就是要找的节点，则直接返回该节点；再向左子树和右子树递归，如果递归回来的结果有一个不为空，则返回这个不为空的结果；如果两个都不为空，则返回这次递归的节点；如果两个都为空，则返回空。

这种解法极大地简化了逻辑判断，并且同时涵盖了要找的两个节点在同一节点下和不在同一节点下的两个情况。

``` python
from typing import Optional

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.recursion(root, p, q)

    def recursion(self, root: TreeNode, p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
        if root is None:
            return None
        if root == p or root is q:
            return root
        left = self.recursion(root.left, p, q)
        right = self.recursion(root.right, p, q)
        if right is not None and left is not None:
            return root
        elif right is None and left is not None:
            return left
        elif right is not None and left is None:
            return right
        else:
            return None
```

代码随想录算法训练营第二十一天 | LeetCode530 二叉搜索树的最小绝对差、LeetCode501 二叉搜索树中的众数、LeetCode236 二叉树的最近公共祖先

今日任务：

1. LeetCode654 最大二叉树
2. LeetCode617 合并二叉树
3. LeetCode700 二叉树中的搜索
4. LeetCode98 验证搜索二叉树



资料来源：

1. [代码随想录 | LeetCode654 最大二叉树](https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode617 合并二叉树](https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html)
3. [代码随想录 | LeetCode700 二叉树中的搜索](https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html)
4. [代码随想录 | LeetCode98 验证搜索二叉树](https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html)
5. [Bilibili | LeetCode 0654.最大二叉树：单调栈の视频演示](https://www.bilibili.com/video/BV14N4y1F7tQ/?spm_id_from=333.337.search-card.all.click&vd_source=32594513468dc2fc44ac3914ffccdc1f)

### 1 LeetCode654 最大二叉树

:::info{title="题目"}
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

 

示例 1：
```
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。
```
示例 2：
```
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
```

提示：

- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- nums 中的所有整数 互不相同
:::

最容易想到的解法是暴力递归，每次找到数组里的最大值创建节点，然后递归调用，缩小数组范围，找到新的最大值来创建新的节点。

:::tip{title="提示"}
注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
:::

``` 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        return self.recursion(nums)

    def recursion(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return TreeNode(val=nums[0])
        else:
            max_num = 0
            max_index = 0
            for i in range(len(nums)):
                if max_num < nums[i]:
                    max_num = nums[i]
                    max_index = i
            root = TreeNode(val=max_num)
            root.left = self.recursion(nums[0:max_index])
            root.right = self.recursion(nums[max_index+1:])
            return root
```      

不容易想到的解法是利用单调栈来做。单调栈的含义可以参考单调队列，就是维护一个递增/递减的栈。它的解法是循环取出数组里的每个元素，然后对每个元素都进行以下操作：

1. 创建该元素的节点
2. 当栈顶元素小于节点元素时，不断弹出栈顶元素，并且将节点元素的左子树连接到被弹出的元素
3. 如果栈顶还有元素，那么该元素一定比目前的节点元素更大，将仍然在栈顶的元素的右子树连接到目前的节点元素
4. 当前元素入栈

该方法的原理可以从循环的过程推理得到。在每次循环中，可以视作将目前的数组扩展一次。这个新加入的元素，要么比所有元素都小，要么是某个“最大值”成为某个子树的根节点。如果比所有元素都小，那么走的就是第三步，在右子树上扩展已经连接好的树；如果是某个“最大值”，那么走的就是第二步，将比自己小的元素连接到自己的左子树上（因为自己处于最右侧），然后扩展比自己大的那个树的右子树。在这个过程中，既确保了每个子树的根节点一定是最大值，又确保了这个元素在数组的位置的左侧的所有元素一定在自己的左子树上。等到所有数组元素循环完毕，栈底的元素既是最大值，也是根节点。

这个过程我还没具体理解是怎么想到的，过程演示见资料来源里的视频链接。

``` python
from collections import deque
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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        stack = deque()
        pointer = None
        for i in nums:
            node = TreeNode(val=i)
            if len(stack) > 0:
                while len(stack) > 0 and stack[-1].val < node.val:
                    pointer = stack.pop()
                    node.left = pointer
            if len(stack) > 0:
                stack[-1].right = node
            stack.append(node)

        return stack[0]
```        

### 2 LeetCode617 合并二叉树

:::info{title="题目"}
给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：
```
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
```
示例 2：
```
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
```

提示：

- 两棵树中的节点数目在范围 [0, 2000] 内
- -104 <= Node.val <= 104
:::

牢记递归三要素：递归函数参数和返回值、终止条件、单次递归逻辑。

``` 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # 节点范围为[0, 2000] 先判空
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        return self.recursion(root1, root2)

    def recursion(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None and root2 is None:  # 终止条件 两边都为空的时候终止
            return None
        elif root1 is None and root2 is not None:
            new_root = TreeNode(val=root2.val)
            new_root.right = self.recursion(None, root2.right)
            new_root.left = self.recursion(None, root2.left)
            return new_root
        elif root2 is None and root1 is not None:
            new_root = TreeNode(val=root1.val)
            new_root.right = self.recursion(root1.right, None)
            new_root.left = self.recursion(root1.left, None)
            return new_root
        else:  # 两边的树都不为空
            new_root = TreeNode(val=root1.val + root2.val)
            new_root.right = self.recursion(root1.right, root2.right)
            new_root.left = self.recursion(root1.left, root2.left)
            return new_root
```          

### 3 LeetCode700 二叉树中的搜索

:::info{title="题目"}
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

 

示例 1:
```
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
```
示例 2:
```
输入：root = [4,2,7,1,3], val = 5
输出：[]
```

提示：

- 树中节点数在 [1, 5000] 范围内
- 1 <= Node.val <= 107
- root 是二叉搜索树
- 1 <= val <= 107
:::

``` 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root
        while True:
            print(node.val)
            if node.val == val:
                return node
            else:
                if node.val > val:
                    if node.left is not None:
                        node = node.left
                        continue
                    else:
                        return None
                else:
                    if node.right is not None:
                        node = node.right
                        continue
                    else:
                        return None
```     

``` 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        return self.recursion(root, val)

    def recursion(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        else:
            if root.val == val:
                return root
            elif root.val > val:
                return self.recursion(root.left, val)
            else:
                return self.recursion(root.right, val)
```                

### 4 LeetCode98 验证搜索二叉树

:::info{title="题目"}
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
 

示例 1：
```
输入：root = [2,1,3]
输出：true
```
示例 2：
```
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
```

提示：

- 树中节点数目范围在[1, 104] 内
- -231 <= Node.val <= 231 - 1
:::

要么中序遍历一趟，检查遍历结果；要么递归，设定节点合理范围而不是单纯比较根节点数字。被提醒之后我倒是想到可能的陷阱了，只是有点不确定。

``` 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.recursion(root)

    def recursion(self, root: Optional[TreeNode], upper: Optional[int] = None, down: Optional[int] = None) -> bool:
        if root is None:
            return True
        else:
            if upper is not None and down is not None:
                if not (down < root.val < upper):
                    return False
            elif upper is None and down is not None:
                if not (root.val > down):
                    return False
            elif upper is not None and down is None:
                if not (upper > root.val):
                    return False
            left_result = self.recursion(root.left, root.val, down)
            right_result = self.recursion(root.right, upper, root.val)
            return left_result and right_result
```

``` 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack = deque()
        val_list = []
        node = root
        stack.append(root)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                val_list.append(node.val)
            else:
                if node.right is not None:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left is not None:
                    stack.append(node.left)
        for i in range(len(val_list) - 1):
            if val_list[i] >= val_list[i + 1]:
                return False
        return True
```

看过文档之后确定陷阱了：

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