主要内容：

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
```

代码随想录算法训练营第十八天 | LeetCode513 找树左下角的值、LeetCode112 路径总和、LeetCode113 路径总和Ⅱ、LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树

今日任务：

1. LeetCode110 平衡二叉树
2. LeetCode257 二叉树的所有路径
3. LeetCode404 左叶子之和



资料来源：

1. [代码随想录 | LeetCode110 平衡二叉树](https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html)
2. [代码随想录 | LeetCode257 二叉树的所有路径](https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html)
3. [代码随想录 | LeetCode404 左叶子之和](https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html)

### 1 LeetCode110 平衡二叉树

:::info{title="题目"}
给定一个二叉树，判断它是否是 
平衡二叉树

示例 1：
```
输入：root = [3,9,20,null,null,15,7]
输出：true
```
示例 2：
```
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
```
示例 3：
```
输入：root = []
输出：true
```

提示：

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

递归+后序秒，高度要从递归函数一层一层传上来，如果有发现传上来的子树高度差超过1的，直接返回-1即可。这个-1最终会返回一开始的函数调用处，根据是否是-1返回True/False就行。

``` 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        result = self.getHeight(root)
        if result == -1:
            return False
        else:
            return True

    def getHeight(self, root: TreeNode) -> int:
        if root is None:
            return 1
        left_height = self.getHeight(root.left)
        if left_height == -1:
            return -1
        right_height = self.getHeight(root.right)
        if right_height == -1:
            return -1
        if abs(right_height - left_height) > 1:
            return -1
        else:
            return 1 + max(right_height, left_height)
```

### 2 LeetCode257 二叉树的所有路径

:::info{title="题目"}
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：
```
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
```
示例 2：
```
输入：root = [1]
输出：["1"]
```

提示：

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

前序+回溯。下面的代码的回溯是直接复制了一个字符串的那种隐式回溯，不太能看的出来，结束一层函数栈，它就自动回溯了。（应该不能叫回溯的，但是要说回溯也行吧）

``` 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if root is None:
            return []
        result = self.get_path(root, "", [])
        return result

    def get_path(self, root: TreeNode, path: str, result: List[str]) -> List[str]:
        if path == "":
            path = str(root.val)
        else:
            path += "->" + str(root.val)
        if root.left is None and root.right is None:  # 是叶子节点
            result.append(path)
            return result
        if root.left is not None:
            result = self.get_path(root.left, path, result)
        if root.right is not None:
            result = self.get_path(root.right, path, result)
        return result
```   

### 3 LeetCode404 左叶子之和

:::info{title="题目"}
给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：
```
输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
```
示例 2:
```
输入: root = [1]
输出: 0
```

提示:

- 节点数在 [1, 1000] 范围内
- -1000 <= Node.val <= 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root is None or (root.left is None and root.right is None):
            return 0
        return self.travelsal(root)

    def travelsal(self, root: TreeNode) -> int:
        # 终止条件
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 0
        left_sum = self.travelsal(root.left)  # 这是为了向下递归 和下一句语句不冲突
        if root.left is not None and root.left.left is None and root.left.right is None:  # 是不是左孩子的判断
            left_sum += root.left.val
        right_sum = self.travelsal(root.right)  # 向下递归
        return left_sum + right_sum  # 返回结果
```

代码随想录算法训练营第十七天 | LeetCode110 平衡二叉树、LeetCode257 二叉树的所有路径、LeetCode404 左叶子之和

今日任务：

1. LeetCode104 二叉树的最大深度
2. LeetCode111 二叉树的最小深度
3. LeetCode222 完全二叉树的节点个数



资料来源：

1. [代码随想录 | LeetCode104 二叉树的最大深度](https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html)
2. [代码随想录 | LeetCode111 二叉树的最小深度](https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html)
3. [代码随想录 | LeetCode222 完全二叉树的节点个数](https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html)

### 1 LeetCode104 二叉树的最大深度

:::info{title="题目"}
给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
```
输入：root = [3,9,20,null,null,15,7]
输出：3
```
示例 2：
```
输入：root = [1,null,2]
输出：2
```

提示：

- 树中节点的数量在 [0, 104] 区间内。
- -100 <= Node.val <= 100
:::

迭代层序秒了。递归前序/后序也能做，不过注意得有回溯的过程。

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

``` python
# n叉树
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from collections import deque


class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        queue = deque()
        node = root
        depth = 0
        queue.append(node)
        while len(queue) != 0:
            size = len(queue)
            if size != 0:
                depth += 1
            for _ in range(size):
                node = queue.popleft()
                if node is not None:
                    for i in node.children:
                        queue.append(i)
        return depth
```  

### 2 LeetCode111 二叉树的最小深度

:::info{title="题目"}
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：
```
输入：root = [3,9,20,null,null,15,7]
输出：2
```
示例 2：
```
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
```

提示：

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

迭代层序一样秒了。前序/后序一样能做，前序要注意回溯，后序要注意的是返回值是高度，遇到左子树和右子树中只有一个为空的时候，高度要取那个不为空的子树的高度+1，不能直接对这俩取最小值。

``` 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        node = root
        queue = deque()
        min_depth = 0
        queue.append(node)
        while len(queue) != 0:
            size = len(queue)
            min_depth += 1
            for _ in range(size):
                node = queue.popleft()
                if node.right is None and node.left is None:
                    return min_depth
                else:
                    if node.right is not None:
                        queue.append(node.right)
                    if node.left is not None:
                        queue.append(node.left)
```   

### 3 LeetCode222 完全二叉树的节点个数

:::info{title="题目"}
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：
```
输入：root = [1,2,3,4,5,6]
输出：6
```
示例 2：
```
输入：root = []
输出：0
```
示例 3：
```
输入：root = [1]
输出：1
```

提示：

- 树中节点的数目范围是[0, 5 * 104]
- 0 <= Node.val <= 5 * 104
- 题目数据保证输入的树是 完全二叉树
 

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
:::

简单一点的，就是按照随便一种二叉树遍历方式，把整个二叉树都遍历一次。如果是进阶要求的话，可以利用完全二叉树的特性进行计算。

完全二叉树无非两种情况：要么最后一层是满的，要么最后一层没满。如果满了，那么就能使用公式$2 ^ {树深度} - 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 countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return self.countNodes_recursion(root)

    def countNodes_recursion(self, root: TreeNode) -> int:
        left_count = 0
        if root.left is not None:
            if self.is_complete(root.left):  # 判断左子树是不是满二叉树
                left_count = self.count_complete_tree(root.left)  # 是的话直接调公式
            else:
                left_count = self.countNodes_recursion(root.left)  # 不是的话再递归分解
        right_count = 0
        if root.right is not None:  # 同上
            if self.is_complete(root.right):
                right_count = self.count_complete_tree(root.right)
            else:
                right_count = self.countNodes_recursion(root.right)
        return 1 + left_count + right_count

    def count_complete_tree(self, root: TreeNode) -> int:
        pointer = root
        left_depth = 0
        while pointer is not None:  # 计算深度
            left_depth += 1
            pointer = pointer.left
        return 2 ** left_depth - 1  # 公式

    def is_complete(self, root: TreeNode) -> bool:  # 判断是不是满二叉树
        pointer = root
        left_depth = 0
        right_depth = 0
        while pointer is not None:
            left_depth += 1
            pointer = pointer.left
        pointer = root
        while pointer is not None:
            right_depth += 1
            pointer = pointer.right
        return left_depth == right_depth
```

代码随想录算法训练营第十六天 | LeetCode104 二叉树的最大深度、LeetCode111 二叉树的最小深度、LeetCode222 完全二叉树的节点个数 

今日任务：

1. 二叉树的层序遍历
2. LeetCode226 翻转二叉树
3. LeetCode101 对称二叉树



资料来源：

1. [代码随想录 | 二叉树的层序遍历](https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html)
2. [代码随想录 | LeetCode226 翻转二叉树](https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html)
3. [代码随想录 | LeetCode101 对称二叉树](https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html)

### 1 二叉树的层序遍历

:::info{title="题目"}
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
```
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
```
示例 2：
```
输入：root = [1]
输出：[[1]]
```
示例 3：
```
输入：root = []
输出：[]
```

提示：

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

这道题同107、199、637、429、515、116、117、104、111，都是层序遍历和它的各种修改版本。116和117有别的写法，可以利用已经建立的next指针来进行优化。

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

### 2 LeetCode226 翻转二叉树

:::info{title="题目"}
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
```
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
```
示例 2：
```
输入：root = [2,1,3]
输出：[2,3,1]
```
示例 3：
```
输入：root = []
输出：[]
```

提示：

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

挨个节点交换左右孩子即可，层序秒了。另外注意，如果要用中序，按照以往的写法，左子树会被翻转两次。处理完左子树，交换左右子树之后，还得翻转左子树才行。

``` 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        queue = deque()
        node = root
        queue.append(node)
        while len(queue) != 0:
            node = queue.popleft()
            temp = node.left
            node.left = node.right
            node.right = temp
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        return root
```        

### 3 LeetCode101 对称二叉树

:::info{title="题目"}
给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
```
输入：root = [1,2,2,3,4,4,3]
输出：true
```
示例 2：
```
输入：root = [1,2,2,null,3,null,3]
输出：false
```
提示：

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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？
:::

一开始是想写迭代的，然后写着写着就一发不可收拾。这个写法同时对根节点的左右子树进行中序和反中序遍历，只要有节点不同就返回False。然后就写成了这样，中间的判断太多了。一开始用层序就好了，那个还好想一些。

``` 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root.right is None and root.left is None:
            return True
        if not (root.right is not None and root.left is not None):
            return False
        stack_left = deque()
        stack_right = deque()
        node = root
        stack_left.append(node.left)
        stack_right.append(node.right)
        while len(stack_left) != 0:
            node_left = stack_left.pop()
            if len(stack_right) == 0:
                return False
            node_right = stack_right.pop()
            if node_left is None:
                node_left = stack_left.pop()
                if len(stack_right) == 0:
                    return False
                node_right = stack_right.pop()
                if node_right is None:
                    return False
                print(node_left.val)
                print(node_right.val)
                if node_left.val != node_right.val:
                    return False
            else:
                if node_left.right is not None:
                    stack_left.append(node_left.right)
                stack_left.append(node_left)
                stack_left.append(None)
                if node_left.left is not None:
                    stack_left.append(node_left.left)

                if node_right is None:
                    return False
                if node_right.left is not None:
                    stack_right.append(node_right.left)
                stack_right.append(node_right)
                stack_right.append(None)
                if node_right.right is not None:
                    stack_right.append(node_right.right)
        if len(stack_right) != 0:
            return False
        return True
```        

文档给的思路就是，递归的时候同时处理两个节点，本质上还是两边同时遍历。比较的时候同时比较外层和内层。对于左子树和右子树来说，这相当于是左右中和右左中的两种后序遍历。

![02aa6e9fbaf88a779ee6d60251a8e64.jpg](https://www.misaka19327.cc/static/img/3c721b446518c86accbfd86f27d2c6db.02aa6e9fbaf88a779ee6d60251a8e64.jpg)

``` 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root.left is None and root.right is None:
            return True
        if not (root.left is not None and root.right is not None):
            return False
        else:
            return self.recursion(root.left, root.right)

    def recursion(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        # 递归终止条件
        if left is None and right is None:
            return True
        if not (left is not None and right is not None):
            return False
        else:
            if left.val != right.val:
                return False

        # 单层递归逻辑
        outside = self.recursion(left.left, right.right)  # 外层
        inner = self.recursion(left.right, right.left)  # 内层
        return outside and inner
```     

这个写迭代也不是不能写，思路和递归版本是一样的，用队列实现（用栈应该也是一个效果）。

``` 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root.left is None and root.right is None:
            return True
        if not (root.left is not None and root.right is not None):
            return False
        else:
            queue = deque()
            queue.append(root.left)
            queue.append(root.right)
            while len(queue) != 0:
                left = queue.popleft()
                right = queue.popleft()
                if left is None and right is None:
                    continue
                if not (left is not None and right is not None):
                    return False
                if left.val != right.val:
                    return False
                queue.append(left.left)
                queue.append(right.right)
                queue.append(left.right)
                queue.append(right.left)
            return True
```        

总之这道题只要悟到了得左右子树同时进行两种后序遍历就很好写。

~~所以我是怎么写的那么史山的……~~