今日任务：

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

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

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

代码随想录算法训练营第十五天 | 二叉树层序遍历、LeetCode226 翻转二叉树、LeetCode101 对称二叉树

今日任务：

1. 二叉树理论基础
2. 递归遍历  
3. 迭代遍历
4. 统一迭代



资料来源：

1. [代码随想录 | 二叉树理论基础](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | 递归遍历](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 迭代遍历](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html)
4. [代码随想录 | 统一迭代](https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E6%80%9D%E8%B7%AF)

### 1 二叉树理论基础

1. **满二叉树**：如果一棵二叉树的所有节点的度要么是0要么是2，并且度为0的节点在同一层上，那么它就是一棵满二叉树。

2. **完全二叉树**：在完全二叉树中，除了最底层以外，其余每层节点数量都达到最大值，并且最下面一层的节点都集中在该层的最左边的若干位置。若最底层为第h层，则该层的节点数不超过$1$到$2^{h-1}$这个范围。

3. **二叉搜索树**：二叉搜索树是一个有序树，它符合以下条件：

     - 若它的左子树不空，则左子树上的所有节点的值均小于它的根节点的值
     - 若它的右子树不空，则右子树上的所有节点的值均大于它的根节点的值
     - 它的左右子树也分别为二叉排序树

4. **平衡二叉搜索树**：AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。

5. **二叉树的遍历方式**：深度优先搜索（DFS，可以前序中序后序，使用栈）、广度优先搜索（BFS，可以层序，使用队列）、前序（中左右，可以递归可以迭代）、中序（左中右，可以递归可以迭代）、后序（左右中，可以递归可以迭代）、层序（可以迭代）。

6. 二叉树的定义

``` python
class TreeNode:
    def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None):
        self.val = val
        self.left = left
        self.right = right
```

### 2 递归遍历

递归的三要素：

1. 递归函数的参数和返回值

2. 终止条件

3. 单层递归的逻辑

以前序遍历为例：

1. 递归函数的参数和返回值：遍历不需要处理数据什么的，所以只需要传入要遍历的节点和存放遍历结果的数据即可。

2. 终止条件：如果当前要遍历的节点是空，遍历就要结束了，这就是终止条件。

3. 单层递归的逻辑：前序遍历是中左右，那就是先遍历中间的，然后调用函数遍历左子树的，最后是右子树的。

根据这三个条件，前序遍历的代码就是这样：

``` 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])  # 进入递归

    def traversal(self, node: Optional[TreeNode], result: List[int]) -> List[int]:  # 参数和返回值
        if node is None:  # 终止条件
            return result
        else:
            # 单层递归的逻辑
            result.append(node.val)
            self.traversal(node.left, result)
            self.traversal(node.right, result)
            return result
```

举一反三，中序和后序的代码也是差不多：

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

    def traversal(self, node: TreeNode, result: List[int]) -> List[int]:
        if node is not None:
            self.traversal(node.left, result)
            result.append(node.val)
            self.traversal(node.right, result)
        return result
```

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

    def traversal(self, node: TreeNode, result: List[int]) -> List[int]:
        if node is None:
            return result
        else:
            self.traversal(node.left, result)
            self.traversal(node.right, result)
            result.append(node.val)
            return result
```     

### 3 迭代遍历

之前的前序，中序和后序遍历都用的递归来写的，而栈又是递归所用的函数栈的底层，那么栈也能替代递归，使得二叉树的遍历不使用递归方式完成。

前序遍历：要先处理的是根节点，之后是左节点，最后是右节点。在栈中也是先弹出当前节点进行处理，然后加入它的左节点和右节点，下次循环再出栈一个元素。

``` 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = deque()
        if root is None:
            return []
        result = []
        node = root
        stack.append(node)
        while node is not None and len(stack) != 0:
            node = stack.pop()
            result.append(node.val)
            if node.right is not None:  # 栈是先进后出 所以先进右节点
                stack.append(node.right)
            if node.left is not None:
                stack.append(node.left)

        return result
```        

中序遍历：这次维护的栈，必须保证栈顶是目前子树中最“左”的节点，如果已经指到叶子节点了，之后指向空了，就可以从栈中取出元素，处理并且指向右节点了。

``` 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        while node is not None or len(stack) != 0:
            if node is not None:  # 这一部分的目的是先让栈顶存着目前子树最“左”的节点
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()  # 到这一步可以确定没有再“左”的节点了 从栈中弹出并且处理之前的节点
                result.append(node.val)
                node = node.right
        return result
```     

后序遍历：由于后序遍历的顺序和前序完全相反，所以直接先前序调整一下顺序，然后出了结果反转一下即可。

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

``` python
# 二叉树的后序遍历 迭代写法
from collections import deque
from typing import Optional, List

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            result.append(node.val)
            if node.left is not None:
                stack.append(node.left)
            if node.right is not None:
                stack.append(node.right)
        result.reverse()
        return result
```        

### 4 统一迭代（标记法）

在之前的迭代法中，前、后序和中序的写法有截然不同的区别。这是因为前、后序要处理加入结果数组的节点，和每次循环弹出的节点是一致的，而中序不是一致的。而不一致的解决方法，可以通过在栈中加入标记来解决，因此就有了统一写法的迭代法（也称标记法）。

这种统一写法的迭代法不是很好想，但是优势前中后序改变很容易，也很好记。也需要会写。

``` 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is not None:
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)  # 标记在这里 这个标记的含义是它前面的节点已经被处理 不再需要向下找子节点了
            else:
                node = stack.pop()
                result.append(node.val)  # 因为有标记所以直接加入值
        return result
```        

``` 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                result.append(node.val)
            else:
                # 相比前序 只有下面这6行代码有顺序变化
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
        return result
```

``` 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        stack = deque()
        result = []
        node = root
        stack.append(node)
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                result.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)
        return result
```

代码随想录算法训练营第十四天 | 二叉树基础，四种遍历方式

今日任务

1. LeetCode239 滑动窗口最大值
2. LeetCode347 前K个高频元素
3. 栈和队列总结



资料来源

1. [代码随想录 | LeetCode239 滑动窗口最大值](https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode347 前K个高频元素](https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 栈和队列总结](https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html#%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%9A%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80)

### 1 LeetCode239 滑动窗口最大值

:::info{title="题目"}
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：
```
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
 ```
示例 2：
```
输入：nums = [1], k = 1
输出：[1]
```

提示：

- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
:::

解析看最后那一块。

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

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = MonotonousQueue()
        result = [0] * (len(nums) - k + 1)
        for i in range(k - 1):
            queue.append(nums[i])
        for i in range(len(nums) - k + 1):
            queue.append(nums[i + k - 1])
            result[i] = queue.getFirst()
            if nums[i] == queue.getFirst():
                queue.pop(nums[i + k - 1])
        return result


class MonotonousQueue:
    def __len__(self):
        return len(self.queue)

    def __init__(self):
        self.queue = deque()

    def getFirst(self):
        return self.queue[0]

    def pop(self, number: int):
        self.queue.popleft()
        if len(self.queue) > 0:
            while self.queue[0] < number:
                self.queue.popleft()

    def append(self, number: int):
        if len(self.queue) == 0:
            self.queue.append(number)
            return
        while self.queue[-1] < number:
            self.queue.pop()
            if len(self.queue) == 0:
                break
        self.queue.append(number)
```

### 2 LeetCode347 前K个高频元素

:::info{title="题目"}
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:
```
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
```
示例 2:
```
输入: nums = [1], k = 1
输出: [1]
```

提示：

- 1 <= nums.length <= 105
- k 的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
:::

解析看最后那一块。

``` python
import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = dict()
        for i in nums:
            if i in map.keys():
                map[i] += 1
            else:
                map[i] = 1

        pri_que = []

        for key, freq in map.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k:
                heapq.heappop(pri_que)

        result = []
        for i in pri_que:
            result.append(i[1])
        return result
```     

### 3 栈和队列总结

#### 3.1 栈题目

栈的先进后出的特性，使得它能够快速的解决一些邻近的捉对问题，比如说之前的查括号是否都是一对一对的，或者说删除相邻相同字符。另外在一些要保留之前元素顺序的同时对当前元素和之前的若干个元素进行处理的话，栈也是值得考虑的一种解法，就比如之前的逆波兰表达式。

栈在一些比较底层的程序应用上常见，比如说解析文件路径，再比如说程序运行的函数调用栈。

#### 3.2 队列题目

先说单调队列。

单调队列是一个视情况而定的队列，它的目的一般是使队列里的元素递增或者递减。单调队列并没有一种固定的实现，**甚至并不固定是先出先进还是先出后进**，根据题目要求来灵活制定pop和append的行为。以今天的题目为例，它就维护了一个名为单调队列，实则为双端队列的数据结构。

这题目要求求滑动窗口中的最大值，那么很明显是要维护一个递减的单调序列，每次要实际求的是最大值。对应到具体的单调队列上，append元素之前就要保证之前的所有元素都比自己大，所以append的行为就是从队列右端一个一个取值和要加入的元素进行比较，直到前面的元素都比自己大为止；pop元素就是要在窗口滑出最大值的时候再pop。

再说大小顶堆/优先级队列。

它和单调队列不一样，单调队列的目的是保证每次pop元素的时候一定pop出最大/最小的那个，而优先级队列则是真的要对元素全部排序。堆对应的是完全二叉树，大顶堆对应的是根节点是最大值，队列就是降序排列；小顶堆对应的根节点是最小值，队列就是升序排序。

最后是python里小顶堆对应的库`heapq`的用法。

- 建立堆：heap = [] 就使用列表就可以
- 将一个队列加入堆/变成小顶堆：heappush(heap, array)/heapify(heap)
- 弹出元素：heappop(heap)
- 获取堆中前num个的最大值/最小值：nlargest(num, heap)/nsmallest(num, heap)
- 合并两个有序数组：merge(sorted(array1), sorted(array2))
- 先加入num元素，再弹出堆顶元素：heapqpushpop(heap, num)
- 先弹出堆顶元素，再加入num元素：heapqreplace(heap, num)