路由与交换技术 记录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)

代码随想录算法训练营第二十三天 | 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
```