今日任务：

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)

代码随想录算法训练营第二十天 | LeetCode654 最大二叉树、LeetCode617 合并二叉树、LeetCode700 二叉树中的搜索、LeetCode98 验证搜索二叉树

主要内容：

1. VLAN说明
2. 三层交换机进行跨VLAN通信配置



~~（内心OS：网上资料怎么这么少啊，华为和思科的设备叫法还不一样，理论上明明用的是一个技术。一开始查的全是华为设备的信息，坑惨我了。）~~

### 1 VLAN 虚拟局域网

:::tip{title="提示"}
以下的内容，如果没有特别标注区分华为和思科设备的话，都是通用的。
:::

在[常见网络设备/概念 && 虚拟机网络三种连接方式说明 && UDP广播 多播](https://www.misaka19327.cc/post/21)这里面提到过，VLAN最主要的目的就是为了划分广播域（这个说法和划分子网个人认为是原理不同但是等效的）。本来一个交换机（如果不明确具体是哪一层工作的交换机，在本文中一律视为二层交换机）只能构建一个广播域，通过VLAN就可以将这个单一网络划分为多个广播域。VLAN的优势在于划分子网和广播域以节省带宽的同时，更加易于管理，网络结构也更加灵活。

#### 1.1 VLAN帧

要使设备能够分辨不同VLAN的报文，需要在报文中添加标识VLAN信息的字段。IEEE 802.1Q协议规定，在以太网数据帧的目的MAC地址和源MAC地址字段之后、协议类型字段之前加入4个字节的VLAN标签（又称VLAN Tag，简称Tag），用以标识VLAN信息。设备利用Tag内的VID来识别数据帧所属的VLAN。

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

Tag结构如下：

- TPID：Tag Protocol Identifier，标签协议标识符，表示数据帧类型。如果该字段取值0x8100，则表示这是IEEE 802.1Q协议下的VLAN数据帧，不支持802.1Q协议的设备接收后会将其丢弃。各个设备厂商也可以自定义该字段的值。
- PRI：Priority，优先级。取值0~7，值越大优先级越高。
- CFI：Canonical Format Indicator，标准格式指示位，表示MAC地址在不同的传输介质中是否以标准格式进行封装。在以太网中，该字段取值为0。
- VID：VLAN ID，表示该数据帧所属VLAN的编号，排除掉协议保留的0和4095，该字段有效取值范围为1~4094。

在一个网络中，以太网帧要么是加了Tag的帧（Tagged），要么没加Tag（Untagged）。在网络设备中，用户终端和Hub只能收发Untagged帧；交换机、路由器和AC能够收发Tagged帧和Untagged帧；语音终端，AP能够同时收发一个Tagged帧和一个Untagged帧。

**华为设备内部处理的数据帧一律都是Tagged帧，思科设备只有Trunk接口出来的数据帧是Tagged帧。**

> 本文中，设备一般指网络设备，如路由器，交换机等网络中间设备；用户终端一般指个人电脑，服务器等网络末端设备。

> AC（Wireless Access Point Controller）：接入控制器，负责汇集来自区域内无线网络中的所有AP的数据并接入网络，还负责管理所有AP的网络设备。**不严谨的说**，可以看作无线网络版本的路由器。

> AP（Wireless Access Point）：无线网络接入点，是无线网络版本的交换机，是移动设备进入有线网络的接入点。

#### 1.2 链路类型和接口类型

**链路类型**：

- 接入链路（链路两端是Access接口）：只能承载一个VLAN的链路，用于连接设备和用户终端。通常情况下，**用户终端并不需要知道自己属于哪个VLAN，也不能识别带有Tag的帧**，所以在接入链路上传输的帧都是Untagged帧。
- 干道链路（Trunk链路，链路两端是Trunk接口）：可以承载多个VLAN的链路，用于设备间互连。为了保证其它网络设备能够正确识别数据帧中的VLAN信息，在干道链路上传输的数据帧都必须是Tagged帧。

**接口类型**：

- Access接口：一般用于和不能识别Tag的用户终端（如用户主机、服务器等）相连，或者不需要区分不同VLAN成员时使用。它只能收发Untagged帧，且只能为Untagged帧添加唯一VLAN的Tag。
- Trunk接口：一般用于连接交换机、路由器、AP以及可同时收发Tagged帧和Untagged帧的语音终端。它可以允许多个VLAN的帧带Tag通过，但只允许一个VLAN的帧从该类接口上发出时不带Tag。
- Hybrid接口：Access接口和Trunk接口的使用场景，Hybrid接口都能用。它可以允许多个VLAN的帧带Tag通过，也允许根据配置决定哪些VLAN的帧必须带Tag从该接口发出，哪些VLAN的帧可以不带Tag从该接口发出。

~~大部分情况下，Hybrid接口和Trunk接口能混用，但是在某些情况下，必须使用Hybrid接口，比如说一个接口连接不同VLAN网段的场景中，因为该接口需要给多个Untagged报文添加Tag，所以必须使用Hybrid接口。~~ **这段目前存疑。**

（思科设备不清楚有没有Hybrid接口，就先当是有吧）

**缺省VID（PVID）**：由于设备处理的数据帧都带Tag，当设备收到Untagged帧时，就需要给该帧添加Tag，添加什么Tag，就由接口上的缺省VLAN决定。

- Access接口：PVID即为它允许通过的VLAN的VID。
- Trunk接口和Hybrid接口：PVID需要另外配置。一个接口允许多个VLAN通过，但是PVID只能有一个。

**本征VLAN（Native VLAN）（仅限思科设备）**：这个概念和PVID很接近，但是是两个概念。**它的目的是为了维护Untagged数据的向下兼容性**，是Trunk链路两端的公共标识符，可以通过`show interfaces f0/1 switchport`来查看。默认情况下，思科设备的Trunk和Hybrid接口的本征VLAN的VID为1。（目前它的具体行为还是未知）

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

**管理VLAN（仅限思科设备）**：它是方便远程管理交换机用的，默认是VLAN1。通过它，终端设备可以直接远程对交换机进行配置。也因此，最好不要将自定义的VLAN的VID配置成1。

**接口行为**：

| 接口类型 | 接收Untagged帧的行为（由用户终端发送） | 接收Tagged帧的行为（由设备发送） | 发送帧的具体行为 |
| --- | --- | --- | --- |
| Access接口 | 接收该数据帧，并且打上PVID对应的Tag | 当该数据帧的VID和PVID相同时，接收该数据帧；否则丢弃该帧 | 去掉Tag再发送 |
| Trunk接口 | 先打上PVID对应的Tag。如果PVID在允许通过的VID列表里，就接收该帧，反之则丢弃 | 如果Tagged帧的VID在允许通过的VID列表里，就接收该帧，反之则丢弃 | 当发送帧的VID和PVID**相同**，并且在允许通过的VID列表里，则去掉Tag并且发送该帧；当发送帧的VID和PVID**不同**，并且在允许通过的VID列表里，则保持原有的Tag再发送 |
| Hybrid接口（这一行仅限华为设备） | 同Trunk接口 | 同Trunk接口 | 当发送帧的VID在允许通过的VID列表里，就发送该帧。可以通过命令来配置发送时是否携带Tag发送 |

#### 1.3 VLAN内互访

:::tip{title="提示"}
以下内容对华为设备有效，思科设备不清楚。猜测也仅有在数据帧进入和送出交换机时，是否打Tag有区别。思科设备只会在数据帧从Trunk接口发出时打上Tag，其他部分应该都是一致的。
:::

~~要是现场有个思科设备让我抓包我也不至于一个劲猜了。~~

同一VLAN内的用户互访一般会经过以下三个环节：

1. **用户主机的报文转发**：源主机在发起通信之前，会将自己的IP与目的主机的IP进行比较，如果两者位于同一网段，会尝试获取目的主机的MAC地址，并将其作为目的MAC地址封装进报文；如果两者位于不同网段，源主机会获取网关的MAC地址，并将其作为目的MAC地址封装进报文，以将报文递交给网关。
2. **设备内部的以太网交换**：
    - 如果目的MAC地址+VID能够匹配自己的MAC表且三层转发标志置位，则进行三层交换，会根据报文的目的IP地址查找三层转发表项，如果没有找到会将报文上送CPU，由CPU查找路由表实现三层转发。
    - 如果目的MAC地址+VID能够匹配自己的MAC表但三层转发标志未置位，则进行二层交换，会直接将报文根据MAC表的出接口发出去。
    - 如果目的MAC地址+VID不能匹配自己的MAC表，则进行二层交换，此时会向所有允许VID通过的接口广播该报文，以获取目的主机的MAC地址。
3. **设备之间交互时，VLAN标签的添加和剥离**：设备内部的以太网交换都是带Tag的，为了与不同设备进行成功交互，设备需要根据接口的设置添加或剥除Tag。不同接口VLAN标签添加和剥离情况不同。

***

同设备下VLAN内互访：

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

当用户主机PC0发送报文给用户主机PC1时，报文的发送过程如下（假设Switch0上还未建立任何转发表项）：

1. PC0判断目的IP地址跟自己的IP地址在同一网段，于是发送ARP广播请求报文获取目的主机PC1的MAC地址，报文目的MAC填写全F，目的IP为PC1的IP地址192.168.1.11。
2. 报文到达Switch0的接口F0/1，发现是Untagged帧，给报文添加VID=10的Tag（Tag的VID=接口的PVID），然后根据报文的源MAC地址、VID和报文入接口（PC0的MAC地址、10、F0/1）生成MAC表。
3. 根据报文目的MAC地址+VID查找Switch0的MAC表，没有找到，于是在所有允许VLAN2通过的接口中（比如F0/2）广播该报文。
4. 接口F0/2在发出ARP请求报文前，根据接口配置（Access），剥离VID=10的Tag。
5. PC1收到该ARP请求报文，将PC0的MAC地址和IP地址对应关系记录ARP表。然后比较目的IP与自己的IP，发现跟自己的相同，就发送ARP响应报文，报文中封装自己的MAC地址，目的IP为PC0的IP地址192.168.1.10。
6. Switch0的接口F0/2收到ARP响应报文后，同样给报文添加VID=10的Tag。
7. Switch0根据报文的源MAC地址、VID和报文入接口（PC1的MAC地址，10，F0/2）生成MAC表，然后根据报文的目的MAC地址+VID（PC0的MAC地址，10）查找MAC地址表，由于前面已记录，查找成功，向出接口F0/1转发该ARP响应报文。
8. Switch0向出接口F0/1转发前，同样根据接口配置（Access）剥离VID=10的Tag。
9. PC0收到PC1的ARP响应报文，将PC1的MAC地址和IP地址对应关系记录ARP表。

*** 

不同设备间VLAN内互访：

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

1. 经过和**同设备下VLAN内互访内第一、二步**一样的过程后，报文被广播到Switch0的F0/2接口。
2. Switch0的F0/2接口在发出ARP请求报文前，因为接口的PVID=1（缺省值），与报文的VID（10）不相等，直接传送该报文到Switch1的F0/1接口，不剥除报文的Tag。
3. Switch1的F0/1接口收到该报文后，判断报文的Tag中的VID=10是接口允许通过的VLAN，接收该报文。
4. 经过与**同设备VLAN内互访内的第三到六步**一样的过程后，Switch1将向其出接口F0/1转发PC2的ARP响应报文，转发前，因为接口F0/1为Trunk接口且PVID=1（缺省值），与报文的VID不相等，直接透传报文到Switch0的F0/2接口。
5. Switch0的F0/2接口收到PC2的ARP响应报文后，判断报文的Tag中的VID=10是接口允许通过的VLAN，接收该报文。后续处理同**同设备VLAN内互访的第七步到第九步**一样。

#### 1.4 VLAN间互访

这一段华为和思科的设备说法不一，但是大体的理论基础都是**为VLAN设置一个虚拟的接口**，然后把网关设置到这个虚拟的接口上，开始路由/三层转发。思科的设备叫这个虚拟接口为SVI（Switched Virtual Interface），华为的可以设置两种接口，一个是VLANIF接口，和思科的SVI接口有点类似；另一个是Dot1q终结子接口，它能把多个VLAN都接到这一个虚拟接口上，不消耗IP地址，但是网络繁忙时有可能会成为通信瓶颈。

以思科的设备为例，一种方法是传统路由来实现，结构是这样子：

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

一种方法是单臂路由，拓扑和上面那个方法差不多，就是路由器和交换机之间只有一根线，能同时传多个VLAN的数据。

另一种方法是基于三层交换机来做，结构是这样：

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

单臂的理论基础，简单来说就是用户终端网关到路由，由路由表匹配到另一个VLAN对应的路由接口，从该接口再出发去目的地。它的理论足够简单，但是问题在于VLAN间通信一次，单臂的这个“臂”上通信就要传两次数据，还带一次路由的时间，在网络繁忙的时候极其容易成为通信速度的瓶颈。

三层路由的理论基础就是，在三层路由器上配置SVI，然后用户终端网关到这个SVI上。需要VLAN间互访时，数据帧到了实际和这个用户终端相连的物理接口上，会被转给路由模块的虚拟接口上，再路由到另一个VLAN对应的虚拟接口上再转发出去。大体是这样的：

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

### 2 三层交换机进行跨VLAN通信配置示例

拓扑图：

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

:::tip{title="提示"}
3560三层交换机拖上去就直接开机了。3650不行，必须把电源模块拖上去才行：

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

四个PC机配置IP略。

交换机配置示例如下：

```
enable
config t
vlan 10 // 创建vlan
exit
vlan 20
exit
interface fa0/1 // 配置fa0/1接口
switchport access vlan 10 // 接口是access模式 允许vlan10通过
exit 
interface fa0/2
switchport access vlan 20
exit
interface fa0/3
switchport mode trunk // 配置接口为trunk模式
switchport trunk allowed vlan all // trunk模式下 允许所有vlan通过
```

三层交换机配置示例如下：

```
enable
config t
vlan 10
exit
vlan 20
exit
interface g1/0/1
switchport mode trunk // 配置接口为trunk模式
switchport trunk allowed vlan all // trunk模式下 允许所有vlan通过
exit
interface vlan 10 // 创建SVI
ip address 192.168.10.10 255.255.255.0 // 配置SVI的ip地址
exit
interface vlan 20 // 创建SVI
ip address 192.168.20.10 255.255.255.0 // 配置SVI的ip地址
exit
ip routing // 开启三层交换机的路由功能
```

配置完成后vlan之间可以互相通信，三层交换机处可以看到路由信息（`do show ip route`）。

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

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

### 3 资料来源

[VLAN基础知识](https://cshihong.github.io/2017/11/05/VLAN%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/)

[VLAN端口类型详解——Huawei、Cisco](https://juejin.cn/post/6997998042477494308)

[思科Native vlan（本征VLAN）](http://blog.chinaunix.net/uid-26893608-id-3755555.html)

[林一木
Cisco 交换机配置的基本命令](https://www.cnblogs.com/dream-1314/p/15947568.html)

[cisco（三层交换和动态路由，不同vlan间的通信，静态路由实现全网互通）](https://zhuanlan.zhihu.com/p/35294589)

[三个案例场景带你掌握Cisco交换机VLAN互通](https://cloud.tencent.com/developer/article/2377672)

[2万字18图带你详解VLAN技术](https://zhuanlan.zhihu.com/p/616406502)

[Cisco | 使用外部路由器配置 VLAN 间路由](https://www.cisco.com/c/zh_cn/support/docs/lan-switching/inter-vlan-routing/14976-50.html)

[思科vlan与华为vlan 介绍以及配置命令对比](https://blog.csdn.net/weixin_44809632/article/details/106124567)

[请问这个命令的出处在哪里？（encapsulation dot1Q vlan-id primary～）](https://community.cisco.com/t5/%E8%B7%AF%E7%94%B1%E8%AE%A8%E8%AE%BA%E5%8C%BA/%E8%AF%B7%E9%97%AE%E8%BF%99%E4%B8%AA%E5%91%BD%E4%BB%A4%E7%9A%84%E5%87%BA%E5%A4%84%E5%9C%A8%E5%93%AA%E9%87%8C-encapsulation-dot1q-vlan-id-primary/td-p/4334934)

路由与交换技术 记录1

今日任务：

1. LeetCode513 找树左下角的值
2. LeetCode112 路径总和、LeetCode113 路径总和Ⅱ
3. LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树



资料来源：

1. [代码随想录 | LeetCode513 找树左下角的值](https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode112 路径总和、LeetCode113 路径总和Ⅱ](https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html)
3. [代码随想录 | LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树](https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%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)

### 1 LeetCode513 找树左下角的值

:::info{title="题目"}
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

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

提示:

* 二叉树的节点个数的范围是 [1,104]
* $-2^{31}$ <= Node.val <= $2^{31} - 1$
:::

这题确实是迭代简单得多，第一次做的时候直接迭代出的结果。先在队列里迭代到最后一层，然后在向队列中添加元素的时候，故意将左侧元素放在右侧元素后面添加，这样最后遍历到的元素一定会因为是叶子元素而修改result，也一定是最左侧的元素。

另外，这题不能使用先放左侧元素后放右侧元素，遇到叶子节点直接返这样的方法，防的是这样的二叉树：

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

``` 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = deque()
        queue.append(root)
        result = 0
        while len(queue) != 0:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                if node.left is None and node.right is None:
                    result = node.val
                if node.right is not None:
                    queue.append(node.right)
                if node.left is not None:
                    queue.append(node.left)
        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.depth = 0
        self.result = 0
        self.max_depth = 0

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

    def traversal(self, root: TreeNode):
        self.depth += 1
        if root.right is None and root.left is None:
            if self.max_depth < self.depth:
                self.max_depth = self.depth
                self.result = root.val
        else:
            # 在这里保证了优先找左节点 所以一旦到达了更深的一层 在上面的代码中第一个被更新的一定是左节点
            if root.left is not None:
                self.traversal(root.left)
                self.depth -= 1  # 回溯
            if root.right is not None:
                self.traversal(root.right)
                self.depth -= 1  # 回溯
```                

### 2 LeetCode112 路径总和、LeetCode113 路径总和Ⅱ

:::info{title="题目"}
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

（路径之和Ⅱ要求返回满足targetSum的所有路径）

示例 1：
```
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
```
示例 2：
```
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
```
示例 3：
```
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
```

提示：

- 树中节点的数目在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
:::

一眼递归，记得回溯即可。这个题也有迭代写法，用栈模拟递归即可。

``` 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.sum = 0

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        return self.traversal(root, targetSum)

    def traversal(self, root: TreeNode, targetSum: int) -> bool:
        self.sum += root.val  # 进入下一个节点
        if root.left is None and root.right is None:
            return self.sum == targetSum
        left = False
        if root.left is not None:
            left = self.traversal(root.left, targetSum)
            self.sum -= root.left.val # 回溯
        right = False
        if root.right is not None:
            right = self.traversal(root.right, targetSum)
            self.sum -= root.right.val # 回溯
        if left or right:
            return True
        else:
            return False
```

``` python
# 路径之和Ⅱ
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.path = []

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []
        self.traversal(root, targetSum)
        return self.result_

    def traversal(self, root: TreeNode, targetSum: int):
        self.path.append(root.val)
        if root.right is None and root.left is None:
            if sum(self.path) == targetSum:
                self.result_.append(self.path.copy())  # copy必须 否则进去的只有地址
                return
        if root.left is not None:
            self.traversal(root.left, targetSum)
            self.path.pop()  # 回溯
        if root.right is not None:
            self.traversal(root.right, targetSum)
            self.path.pop()  # 回溯
```        

### 3 LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树

:::info{title="题目"}
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

（第二个题给的就是前序和中序遍历序列）

示例 1:
```
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
```
示例 2:
```
输入：inorder = [-1], postorder = [-1]
输出：[-1]
```

提示:

- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder 和 postorder 都由 不同 的值组成
- postorder 中每一个值都在 inorder 中
- inorder 保证是树的中序遍历
- postorder 保证是树的后序遍历
:::

总的原理就是利用后序/前序的根节点在最后/最前的特性对中序和后序/前序序列进行切割，将左子树和右子树的序列切割出来。大体上就是这么一个步骤：

1. 如果传入的序列长度为0，说明已经到头了，直接返回None
2. 如果传入的序列长度为1，说明到的是叶子节点，按照这个序列里唯一的元素创建节点返回即可。
3. 在其他情况下，要将传入的序列分割为左子树、根节点和右子树。利用后序/前序先找到根节点并且创建节点，再利用这个根节点的值在中序序列里寻找对应的元素位置。这个元素位置是可以将中序和后序/前序序列一起切开的（因为两个序列的左子树，右子树序列长度一定相等！）
4. 将后序/前序序列和中序序列的左子树/右子树部分分别进行下一层的递归，并且让根节点的左右子节点指向下一层递归的返回值。

``` 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        return self.traversal(inorder, postorder)

    def traversal(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder) == 0:
            return None
        if len(postorder) == 1:
            return TreeNode(val=postorder[0])
        else:
            node = TreeNode(val=postorder[-1])
            # 先切中序 这个index定到了后序的-1 切中序的同时就已经把后序切完了 因为两个遍历的左子树位置是一样的
            inorder_index = 0
            for inorder_index in range(len(inorder)):
                if inorder[inorder_index] == postorder[-1]:
                    break
            node.left = self.traversal(inorder[0:inorder_index], postorder[0:inorder_index])
            node.right = self.traversal(inorder[inorder_index+1:], postorder[inorder_index:-1])
            return node
```    

``` 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        return self.traversal(preorder, inorder)

    def traversal(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(val=preorder[0])
        else:
            node = TreeNode(val=preorder[0])
            index = 0
            for index in range(len(inorder)):
                if inorder[index] == preorder[0]:
                    break
            node.left = self.traversal(preorder[1:index+1], inorder[0:index])
            node.right = self.traversal(preorder[index+1:], inorder[index+1:])
            return node
```