代码随想录算法训练营第12天—二叉树01 | ● 理论基础 ● *递归遍历 ● *迭代遍历

二叉树

理论基础

文章讲解：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

二叉树是一种数据结构，常用于递归场景
二叉树：binary tree，每个节点最多有两个子节点（分支），深度为k的二叉树最多有2^k-1个节点（k从1开始）
二叉树的常见类型
- 满二叉树：即节点数达到最大值的二叉树
- 完全二叉树：除最底层节点外其它层节点均满，最底层节点从左到右连续的二叉树
- 二叉搜索树：若有左子树，则左子树上所有节点的值比根节点小，若有右子树，则右子树上所有节点的值比根节点大
- 平衡二叉搜索树：左右无子树或左右子树的高度差小于等于1的二叉搜索树
二叉树的存储方式
- 链式存储：通过左右指针存储子节点（相较于顺序存储更易理解，因此更常用）
- 顺序存储：在内存中连续存储，通常使用数组结构，当前节点i的左子节点为2i+1，右子节点为2i+2
二叉树的遍历方式
- 深度优先遍历：优先往深走，借助栈实现
  - 包括以下三种方式，区别在于把中间节点放在什么顺序，前序就是中左右，中序就是左中右，后序就是左右中
  - 前序遍历（递归法，迭代法）
  - 中序遍历（递归法，迭代法）
  - 后序遍历（递归法，迭代法）
- 广度优先遍历：一层一层地遍历，借助队列实现
  - 层次遍历（迭代法）
二叉树节点结构的定义（这里仅展示链表存储的二叉树结构定义）

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

*递归遍历（对应力扣144/145/94）（二叉树的深度优先遍历）

题目链接/文章讲解/视频讲解：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

考点
- 前序遍历的递归法
- 中序遍历的递归法
- 后序遍历的递归法
我的思路
- 无思路
视频讲解关键点总结
- 递归代码三要素
  - 参数和返回值是什么
    - 二叉树深度优先遍历的参数为当前节点
    - 返回值为储存结果的列表
  - 递归终止条件是什么
    - 如果当前节点为空，则终止继续搜索，返回一个空列表，之后将开始递归、一层一层将节点储存到列表中
  - 单层递归的逻辑是什么
    - 若为前序遍历（中左右），代码返回值为
      - 当前节点的值（列表形式）
      - +
      - 以当前节点的左子节点为参数调用递归函数的返回值（列表形式）
      - +
      - 以当前节点的右子节点为参数调用递归函数的返回值（列表形式）
    - 若为中序遍历（左中右），代码返回值为
      - 以当前节点的左子节点为参数调用递归函数的返回值（列表形式）
      - +
      - 当前节点的值（列表形式）
      - +
      - 以当前节点的右子节点为参数调用递归函数的返回值（列表形式）
    - 若为后序遍历（左右中），代码返回值为
      - 以当前节点的左子节点为参数调用递归函数的返回值（列表形式）
      - +
      - 以当前节点的右子节点为参数调用递归函数的返回值（列表形式）
      - +
      - 当前节点的值（列表形式）
我的思路的问题
- 无
代码书写问题
- 列表可以直接用+进行拼接，生成一个新列表
可执行代码

# 前序遍历-递归-LC144_二叉树的前序遍历
# 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: TreeNode) -> List[int]:
        if not root:
            return []

        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)

        return  [root.val] + left +  right

# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)

        return left + [root.val] + right

# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)

        return left + right + [root.val]

*迭代遍历（对应力扣144/145/94）（二叉树的深度优先遍历）

题目链接/文章讲解/视频讲解：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

考点
- 前序和后序搜索的迭代法实现（使用栈）
我的思路
- 无
视频讲解关键点总结
- 前序（中左右）
  - 首先把根节点加入栈
  - 之后开始循环，循环的终止条件为栈是否为空
  - 循环体内，第一步弹栈，并将弹出节点的值加入储存列表
  - 第二步，如果弹出节点的右子节点不为空，将其压栈
  - 第三步，如果弹出节点的左子节点不为空，将其压栈
  - 继续下一轮循环，直到栈空
  - 返回储存列表
- 后序（左右中）
  - 首先把根节点加入栈
  - 之后开始循环，循环的终止条件为栈是否为空
  - 循环体内，第一步弹栈，并将弹出节点的值加入储存列表
  - 第二步，如果弹出节点的左子节点不为空，将其压栈
  - 第三步，如果弹出节点的右子节点不为空，将其压栈
  - 继续下一轮循环，直到栈空
  - 返回储存列表的倒序列表
- 中序（左中右）
  - 中序的迭代遍历思路与前后序有所不同
    - 中序的迭代遍历，所查询的元素和所操作的元素不相同
    - 此时，单纯使用一个栈能做但不好做，因此额外引入一个指针来完善思路
  - 初始指针cur指向根节点，代指所查询的节点；初始栈为空，储存待操作的节点；初始储存列表为空，储存结果（节点的值）
  - 进入while循环，循环条件为指针和栈有一个不为空就继续
  - while循环内，大体的思路是先一直向左查询直到最左节点，之后逐个向回按照左中右的顺序遍历节点；为实现上述操作，需要进行if else条件判断
    - if里负责处理查询到的情况，若cur指针不为空，此时说明查询到了节点，将该节点压栈，并将cur指针指向cur.left；
    - else里负责处理没查询到的情况，如果所查询的节点为空，此时应该开始弹栈，将栈中保存的上一层节点的值遍历储存到储存列表中，因此令cur=弹栈而出的节点，并将cur.val加入储存列表，之后查询cur是否有右子节点（即cur = cur.right）
  - 循环结束，返回储存列表
我的思路的问题
- 无
代码书写问题
- 无
可执行代码

# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result

# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
       if not root:
           return []
       stack = [root]
       result = []
       while stack:
           node = stack.pop()
           # 中结点先处理
           result.append(node.val)
           # 左孩子先入栈
           if node.left:
               stack.append(node.left)
           # 右孩子后入栈
           if node.right:
               stack.append(node.right)
       # 将最终的数组翻转
       return result[::-1]

# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result