今日任务：

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

资料来源：

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

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

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

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