class Solution:
    def calculate(self, s: str) -> int:
        """
        主函数，初始化共享索引并启动递归
        """
        self.where = 0
        return self._f(list(s), 0)

    # s[i....]开始计算，遇到字符串终止 或者 遇到)停止
    # 返回 : 自己负责的这一段，计算的结果
    # 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    def _f(self, s: List[str], i: int) -> int:
        """
        递归函数，处理一个括号内的或整个表达式的求值
        """
        cur = 0
        numbers = []
        ops = []
        
        while i < len(s) and s[i] != ')': # 未终止且未遇到右括号
            if s[i].isdigit(): # 是数字
                cur = cur * 10 + int(s[i])
                i += 1
            elif s[i] != '(': # 不是左括号
                # 遇到了运算符 + - * /
                self._push(numbers, ops, cur, s[i])
                i += 1
                cur = 0
            else: # 是左括号
                # i (.....)
                # 遇到了左括号！
                # 递归调用 f，计算括号内的结果
                cur = self._f(s, i + 1)
                # 递归返回后，where 指向了 ')' 的位置，i 需要跳到 ')' 之后
                i = self.where + 1
        
        # 如果碰到了右括号，将最后一个数字（或括号运算结果）加入列表，并更新全局索引
        self._push(numbers, ops, cur, '+') # 末尾添加一个 '+' 不影响最终计算
        # 更新全局索引，让上级函数知道从哪继续
        self.where = i
        return self._compute(numbers, ops)

    def _push(self, numbers: List[int], ops: List[str], cur: int, op: str):
        """辅助函数，处理数字和操作符的入栈逻辑，并处理乘除法"""
        if not numbers or ops[-1] == '+' or ops[-1] == '-':
            # 如果是第一个数，或者前一个运算符是+或-，直接入栈
            numbers.append(cur)
            ops.append(op)
        else:
            # 如果前一个运算符是*或/，立即计算
            top_number = numbers[-1]
            top_op = ops[-1]
            if top_op == '*':
                numbers[-1] = top_number * cur
            else: # top_op == '/'
                # Python 的 // 是向下取整，题目要求向零取整
                numbers[-1] = int(top_number / cur)
            ops[-1] = op # 更新操作符

            # 具体例子   
            # 原始：3 * 4 + 5
            #     处理到 * 4 时：
            #     - numbers: [3, 4] → [12] (3*4=12)
            #     - ops: ['*'] → ['+'] (更新操作符)  
            # 这样下一个数字 5 就能正确地与 12 进行加法运算

    def _compute(self, numbers: List[int], ops: List[str]) -> int:
        """辅助函数，计算只有加减法的最终结果"""
        ans = numbers[0]
        for i in range(1, len(numbers)):
            ans += numbers[i] if ops[i - 1] == '+' else -numbers[i]
        return ans

class Solution:
    def decodeString(self, s: str) -> str:
        """
        主函数，初始化共享索引并启动递归
        """
        self.where = 0
        return self._f(list(s), 0)

    # s[i....]开始计算，遇到字符串终止 或者 遇到 ] 停止
    # 返回 : 自己负责的这一段字符串的结果
    # 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    def _f(self, s: list, i: int) -> str:
        """
        递归函数，解码一个层级的字符串
        """
        path = []
        cnt = 0
        while i < len(s) and s[i] != ']':
            if 'a' <= s[i] <= 'z' or 'A' <= s[i] <= 'Z':  # 比较范围
                path.append(s[i])
                i += 1
            elif s[i].isdigit():
                cnt = cnt * 10 + int(s[i])
                i += 1
            else:
                # 遇到 [ 
                # 递归调用 f 来解码括号内的内容
                inner_str = self._f(s, i + 1)
                # 将解码后的子串重复 cnt 次
                path.append(cnt * inner_str)
                # 更新 i 到 ']' 之后的位置
                i = self.where + 1
                # 重置 cnt
                cnt = 0
        
        # 更新全局索引，以便上层函数知道从哪里继续
        self.where = i
        return "".join(path)

from collections import defaultdict

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        """
        主函数，初始化共享索引并启动递归，最后格式化输出
        """
        self.where = 0
        # 调用递归函数获取原子计数的字典
        atom_map = self._f(list(formula), 0)
        
        # 构建最终的输出字符串
        ans = []
        # 按原子名称的字母顺序排序，返回有序表
        for key in sorted(atom_map.keys()):
            ans.append(key) # 先添加原子名称再添加数量
            cnt = atom_map[key]
            if cnt > 1:
                ans.append(str(cnt))
        return "".join(ans)

    def _f(self, s: list, i: int) -> dict:
        """
        递归函数，解析一个层级的分子式，返回一个字典
        """
        ans = defaultdict(int)  # 创建默认字典
        name = []  # 存储当前原子名称
        pre = None  # 历史记录
        cnt = 0
        
        while i < len(s) and s[i] != ')':
            if 'A' <= s[i] <= 'Z' or s[i] == '(':
                # 遇到新单元，先把之前收集的信息处理掉
                self._fill(ans, name, pre, cnt)
                # 重置状态
                name.clear()  # 清空列表中的所有元素
                pre = None
                cnt = 0  # 重置倍数
                
                if 'A' <= s[i] <= 'Z':
                    name.append(s[i])
                    i += 1  # 移动到下一个字符
                else:  # 遇到 (
                    # 递归处理括号内的表达式
                    pre = self._f(s, i + 1)
                    i = self.where + 1
            elif 'a' <= s[i] <= 'z':
                name.append(s[i])
                i += 1
            else:  # 遇到数字
                cnt = cnt * 10 + int(s[i])
                i += 1
        
        # 循环结束，处理最后一个单元
        self._fill(ans, name, pre, cnt)
        # 更新全局索引
        self.where = i
        return ans

    def _fill(self, ans: dict, name: list, pre: dict, cnt: int):
        """辅助函数，将一个解析完的单元（原子或括号）合并到总结果中"""
        if name or pre:
            # 如果没有数字，倍数默认为1
            cnt = 1 if cnt == 0 else cnt
            if name:
                # 如果是原子，直接累加数量
                key = "".join(name)
                ans[key] += cnt
            else:  # 如果是括号内的字典 pre
                # 遍历字典，将其中每个原子的数量乘以倍数 cnt，再累加
                for key, val in pre.items():
                    ans[key] += val * cnt

class Solution:
    def solve(self, s: str):
        """主函数，初始化全局变量"""
        self.where = 0
        return self._f(list(s), 0)
    
    def _f(self, s: list, i: int):
        """递归函数核心模板"""
        # 初始化当前层级的状态变量
        result = []  # 或其他适当的数据结构
        
        while i < len(s) and s[i] != 终止条件:
            if 普通字符处理:
                # 直接处理
                i += 1
            elif 嵌套开始标志:
                # 递归调用处理嵌套
                nested_result = self._f(s, i + 1)
                # 处理递归结果
                result.append(nested_result)
                # 更新位置
                i = self.where + 1
            else:
                # 其他情况处理
                i += 1
        
        # 更新全局位置
        self.where = i
        return result

# where的三个关键作用：
# 1. 记录当前递归函数解析到的位置
# 2. 让上级函数知道下级函数处理到哪里了
# 3. 实现递归层级之间的位置传递

# 遇到嵌套开始标志时：
if s[i] == '(' or s[i] == '[':  # 根据具体问题调整
    # 1. 递归调用处理嵌套内容
    nested_result = self._f(s, i + 1)
    
    # 2. 处理递归返回的结果
    process_nested_result(nested_result)
    
    # 3. 更新当前位置到嵌套结束后
    i = self.where + 1

class Solution:
    def generatePermutation1(self, s: str) -> List[str]:
        """
        主函数，初始化并调用递归函数 f1
        """
        # 使用集合 set 来自动处理重复的子序列
        result_set = set()
        # path 使用列表来模拟 Java 的 StringBuilder，方便添加和删除字符
        path = []
        self._f1(s, 0, path, result_set)
        return sorted(list(result_set))

    def _f1(self, s: str, i: int, path: List[str], result_set: Set[str]):
        """
        递归函数，用于生成所有子序列
        s[i...]，之前决定的路径path，set收集结果时去重
        """
        # base case: 当索引 i 到达字符串末尾时，所有字符都已考虑完毕
        if i == len(s):
            result_set.add("".join(path))
        else:
            # 决策1: 选择当前字符 s[i]
            path.append(s[i])  # 加到路径中去
            self._f1(s, i + 1, path, result_set)
            
            # 回溯：撤销选择，为下一种决策做准备
            path.pop()  # 从路径中移除，删掉最后一个字符
            
            # 决策2: 不选择当前字符 s[i]
            self._f1(s, i + 1, path, result_set)

class Solution:
    def generatePermutation2(self, s: str) -> List[str]:
        """
        主函数，初始化并调用递归函数 f2
        """
        result_set = set()
        # 预先分配一个与原字符串等长的列表作为路径容器
        path = [''] * len(s)
        self._f2(s, 0, path, 0, result_set)
        return sorted(list(result_set))

    def _f2(self, s: str, i: int, path: List[str], size: int, result_set: Set[str]):
        """
        与f1思想相同，但使用不同的方式来维护路径
        这方法不用回溯，因为path是固定长度的列表，size指针来表示有效字符长度
        """
        if i == len(s):
            # path[:size] 表示路径中的有效部分
            result_set.add("".join(path[:size]))
            # path[:size]: 取列表/序列 path 的前 size 个元素（左闭右开，不会越界，超过长度就取到末尾）
            # "".join(...): 用空字符串作为分隔符，把可迭代对象里的“字符串元素”拼接成一个整体字符串
            # result_set.add(...): 将结果添加到集合中，自动去重
        else:
            # 决策1: 选择当前字符 s[i]，将其放入 path 的 size 位置
            path[size] = s[i]
            self._f2(s, i + 1, path, size + 1, result_set) #size+1表明有效字符长度+1，指针后移
            
            # 决策2: 不选择当前字符 s[i]，直接进入下一层递归
            self._f2(s, i + 1, path, size, result_set)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        # 排序是关键，它使得相同的元素相邻，便于后续去重处理
        nums.sort()
        path = [0] * len(nums)
        self._f(nums, 0, path, 0, ans)
        return ans

    def _f(self, nums: List[int], i: int, path: List[int], size: int, ans: List[List[int]]):
        """
        递归函数，生成不重复的组合
        """
        # base case: 当 i 到达数组末尾时，形成一个组合
        if i == len(nums):
            ans.append(path[:size])
        else:
            # 找到下一个不同于 nums[i] 的元素的位置 j
            j = i + 1
            while j < len(nums) and nums[j] == nums[i]:
                j += 1
            
            # 决策1: 当前数 nums[i] 一个都不要
            self._f(nums, j, path, size, ans)
            
            # 决策2: 依次尝试要 1 个、2 个... k 个 nums[i]
            # 从这一段相同数字里，依次选择 1 个、2 个、…、(j-i) 个放入路径，然后递归从 j 开始，即处理下一组数去
            for k in range(i, j):
                path[size] = nums[k]
                size += 1
                # 每次选择后，都从下一个不同的数 j 开始继续递归
                self._f(nums, j, path, size, ans)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        self._f(nums, 0, ans)  # 复用了原数组做路径
        return ans

    def _f(self, nums: List[int], i: int, ans: List[List[int]]):
        """
        递归函数，生成全排列
        核心思想 (交换模型)
        """
        # base case: 当 i 到达数组长度时，一个完整的排列就形成了
        if i == len(nums):
            ans.append(nums[:])  # 将当前排列的副本加入结果列表
        else:
            # 尝试将 i 到 len(nums)-1 的每个数放到 i 位置上
            for j in range(i, len(nums)):
                # 将 nums[j] 换到当前要确定的 i 位置
                self._swap(nums, i, j)
                # 递归去确定下一个位置 i+1
                self._f(nums, i + 1, ans)
                # 回溯：将数组恢复原样，以便 for 循环下一次迭代能正确执行
                self._swap(nums, i, j)

    def _swap(self, nums: List[int], i: int, j: int):
        nums[i], nums[j] = nums[j], nums[i]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        主函数，初始化并调用递归函数
        """
        ans = []
        self._f(nums, 0, ans)
        return ans

    def _f(self, nums: List[int], i: int, ans: List[List[int]]):
        """
        递归函数，生成不重复的全排列
        在交换模型基础上增加剪枝逻辑
        """
        if i == len(nums):
            ans.append(nums[:])
        else:
            # seen 集合用于记录在当前 i 位置上已经尝试过的数字
            seen: Set[int] = set()
            for j in range(i, len(nums)):
                # nums[j]没有来到过i位置，才会去尝试
                if nums[j] not in seen:
                    # 记录下来，表示 nums[j] 这个值已经在 i 位置上用过了
                    seen.add(nums[j])
                    # 交换，将 nums[j] 放到 i 位置
                    self._swap(nums, i, j)
                    # 递归处理下一个位置
                    self._f(nums, i + 1, ans)
                    # 回溯，恢复数组
                    self._swap(nums, i, j)
                    
    def _swap(self, nums: List[int], i: int, j: int):
        nums[i], nums[j] = nums[j], nums[i]

class Solution:
    def reverse(self, stack: List[int]):
        """
        主递归函数，用于逆序整个栈。
        核心思想：
        1. 假设有一个函数 `_bottom_out` 可以移除并返回栈底元素。
        2. `reverse` 函数首先调用 `_bottom_out` 得到栈底元素 `num`。
        3. 然后，递归调用 `reverse` 来逆序剩下的 n-1 个元素的栈。
        4. 最后，将之前取出的栈底元素 `num` 压入已逆序的栈中，此时它就成了新的栈顶。
        """
        if not stack:
            return
        
        # 递归地移除并获取栈底元素
        num = self._bottom_out(stack)
        # 递归地逆序剩余的栈
        self.reverse(stack)
        # 将取出的栈底元素压入栈顶
        stack.append(num)

    def _bottom_out(self, stack: List[int]) -> int:
        """
        辅助递归函数，移除并返回栈底元素，同时保持其他元素顺序不变。
        核心思想：
        1. 弹出栈顶元素 `ans`。
        2. 如果栈空了，说明 `ans` 就是我们想要的栈底元素，返回它。
        3. 如果栈不空，递归调用 `_bottom_out` 获取剩下部分的栈底元素 `last`。
        4. 在递归返回的过程中，将之前弹出的 `ans` 重新压栈，以恢复栈的状态。
        5. 将从递归深处得到的 `last` 一路返回上去。
        """
        ans = stack.pop()
        if not stack:
            return ans  # 如果栈空了，说明ans就是栈底元素
        else:
            last = self._bottom_out(stack)  # 递归获取剩下部分的栈底元素
            stack.append(ans)  # 在递归返回过程中，将之前弹出的ans重新压栈
            return last  # 将从递归深处得到的last一路返回上去

class Solution:
    def sort_stack(self, stack: List[int]):
        deep = self._deep(stack)
        while deep > 0:
            # 找到当前 deep 范围内的最大值
            maximum = self._max(stack, deep)
            # 统计最大值出现的次数
            k = self._times(stack, deep, maximum)
            # 将这 k 个最大值沉底
            self._down(stack, deep, maximum, k)
            # 待排序的深度减少 k
            deep -= k

    def _deep(self, stack: List[int]) -> int:
        """返回栈的深度，不改变栈的数据状况"""
        if not stack:
            return 0
        num = stack.pop()
        deep = self._deep(stack) + 1
        stack.append(num)  # 恢复现场
        return deep

    def _max(self, stack: List[int], deep: int) -> int:
        """从栈当前的顶部开始，往下数deep层，返回这deep层里的最大值"""
        if deep == 0:
            return -float('inf')  # 返回一个极小值作为基准
        num = stack.pop()
        rest_max = self._max(stack, deep - 1)
        current_max = max(num, rest_max)
        stack.append(num)  # 恢复现场
        return current_max

    def _times(self, stack: List[int], deep: int, maximum: int) -> int:
        """返回maximum在deep层中出现的次数，不改变栈的数据状况"""
        if deep == 0:
            return 0
        num = stack.pop()
        rest_times = self._times(stack, deep - 1, maximum)
        times = rest_times + (1 if num == maximum else 0)
        stack.append(num)  # 恢复现场
        return times

    def _down(self, stack: List[int], deep: int, maximum: int, k: int):
        """将k个最大值沉到deep层的底部，剩下的数据状况不变"""
        if deep == 0:
            # 递归到底部时，先把k个最大值压入栈
            for _ in range(k):
                stack.append(maximum)
        else:
            num = stack.pop()
            self._down(stack, deep - 1, maximum, k)
            # 在递归返回时，只把非最大值的元素压回去
            if num != maximum:
                stack.append(num)

class TowerOfHanoi:
    def hanoi(self, n: int):
        """
        汉诺塔问题主函数入口
        """
        if n > 0:
            self._f(n, "左", "右", "中")

    def _f(self, i: int, start: str, end: str, other: str):
        """
        递归函数，解决将 i 个圆盘从 start 移动到 end 的问题
        """
        # base case：如果只有一个圆盘，直接移动
        if i == 1:
            print(f"移动圆盘 1 从 {start} 到 {end}")
        else:
            # 步骤1: 将 i-1 个圆盘从 start 移动到 other
            self._f(i - 1, start, other, end)
            # 步骤2: 移动第 i 个圆盘从 start 到 end
            print(f"移动圆盘 {i} 从 {start} 到 {end}")
            # 步骤3: 将 i-1 个圆盘从 other 移动到 end
            self._f(i - 1, other, end, start)

def recursive_function(parameters):
    # base case: 递归终止条件
    if base_condition:
        return base_result
    
    # 递归调用：分解问题
    result = recursive_function(modified_parameters)
    
    # 处理当前层的逻辑
    current_result = process(result)
    
    return current_result

def backtrack(path, choices):
    # base case
    if satisfied:
        result.append(path[:])  # 收集结果
        return
    
    for choice in choices:
        # 做选择
        path.append(choice)
        backtrack(path, remaining_choices)
        # 撤销选择
        path.pop()

# 对每个元素有选择：要 or 不要
def choose(i, path):
    if i == len(arr):
        process(path)
        return
    
    # 要当前元素
    path.append(arr[i])
    choose(i + 1, path)
    path.pop()
    
    # 不要当前元素
    choose(i + 1, path)

# 全排列问题
def permute(arr, i):
    if i == len(arr):
        process(arr)
        return
    
    for j in range(i, len(arr)):
        swap(arr, i, j)
        permute(arr, i + 1)
        swap(arr, i, j)  # 回溯

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

from collections import deque
from typing import List, Optional

# 提交时把方法名改为levelOrder，此方法为普通bfs（宽度/广度优先搜索，叫宽度搜索的原因是层的最大节点数为宽度），此题不推荐
def levelOrder1(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：标准的广度优先搜索（BFS）。
    # 使用一个队列存储待访问节点，同时用一个哈希表（字典）来记录每个节点所在的层级。
    ans = []
    if root:#根节点有东西
        # Python的deque是一个高效的双端队列，非常适合用于BFS
        queue = deque([root])
        # 字典用于存储 node -> level 的映射
        levels = {root: 0}
        while queue:# 队列不空的时候从队列中取出一个节点
            cur = queue.popleft()
            level = levels[cur]                
            # 如果当前层级是第一次遇到，就在ans中创建一个新列表
            if len(ans) == level: #ans 列表的长度总是等于当前已经处理过的层级数量，包括第0层，说明当前节点的层级 level 正好等于已经创建的层级数量，味着这个层级还没有被处理过，需要创建新的列表
                ans.append([])               
            # 将当前节点的值加入对应层级的列表
            ans[level].append(cur.val)              
            # 将子节点加入队列，并记录它们的层级
            if cur.left:
                queue.append(cur.left)
                levels[cur.left] = level + 1
            if cur.right:
                queue.append(cur.right)
                levels[cur.right] = level + 1
    return ans
    # 核心思想：标准的广度优先搜索（BFS），使用一个队列存储待访问节点，
    # 同时用一个哈希表（字典）来记录每个节点所在的层级。

def levelOrder2(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：优化的广度优先搜索（BFS），按层处理。
    # 外层while循环控制层级，内层for循环精确地处理当前层的所有节点。
    # 这样就无需额外的哈希表来存储节点的层级信息。
    ans = []
    if root:
        queue = deque([root])
        while queue: # 当队列不为空，说明还有节点待处理
            size = len(queue) # 当前层的节点数量
            level_list = []
            for _ in range(size): # 精确处理当前层的所有节点
                cur = queue.popleft()
                level_list.append(cur.val)
                if cur.left: # 将下一层节点入队
                    queue.append(cur.left) 
                if cur.right:
                    queue.append(cur.right) # append是加在右边的
            ans.append(level_list)
    return ans

# 提交以下的方法
# 用每次处理一层的优化bfs就非常容易实现
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：在按层BFS的基础上，增加一个布尔标记 `reverse`。
    # 每一层遍历结束后，根据 `reverse` 的值决定是否要将当前层收集到的节点值列表进行反转。
    # 然后切换 `reverse` 的状态，供下一层使用。
    ans = []
    if root:
        queue = deque([root])
        # false 代表从左往右
        # true 代表从右往左
        reverse = False
        while queue:
            size = len(queue)
            level_list = []
            
            # 步骤1: 像常规的按层BFS一样，先收集当前层的所有节点值
            for _ in range(size):
                cur = queue.popleft()
                level_list.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            
            # 步骤2: 根据reverse标记决定是否反转当前层的列表
            if reverse:
                level_list.reverse()
            
            # 步骤3: 将处理好的层列表加入结果，并切换reverse标记
            ans.append(level_list)
            reverse = not reverse
    return ans

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    # 核心思想：给每个节点进行编号，就像在一个完全二叉树中一样。
    # 根节点编号为1，其左子节点为 2*i，右子节点为 2*i + 1。
    # 每一层的宽度就等于该层最右边节点的编号减去最左边节点的编号，再加1。
    # 我们使用按层BFS来遍历，同时在队列中存储 (节点, 编号) 对。
    if not root:
        return 0

    ans = 1
    # 队列中存储 (节点, 节点编号) 的元组
    queue = deque([(root, 1)])
    
    while queue:
        size = len(queue)
        # 记录当前层的起始编号
        start_id = queue[0][1]
        
        # 遍历当前层的所有节点
        for i in range(size):
            node, node_id = queue.popleft()
            
            # 在遍历到当前层最后一个节点时，计算宽度，这个是额外的步骤
            if i == size - 1:
                ans = max(ans, node_id - start_id + 1)

            # 将子节点及其新编号加入队列
            if node.left:
                queue.append((node.left, node_id * 2))
            if node.right:
                queue.append((node.right, node_id * 2 + 1))
    return ans

def maxDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

def minDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        # 当前的树是空树
        return 0
        
    left_depth = self.minDepth(root.left)
    right_depth = self.minDepth(root.right)

    # case 1: 如果左子树或右子树为空，我们不能取它为最小值（因为那条路没有叶子）。
    # 此时必须走另一条非空的路。`left_depth + right_depth + 1` 巧妙地处理了
    # (左=0, 右=N) -> N+1 和 (左=N, 右=0) -> N+1 的情况。
    if left_depth == 0 or right_depth == 0:
        return left_depth + right_depth + 1
    
    # case 2: 如果左右子树都不为空，那么最小深度就是两者中的较小值加1。
    return min(left_depth, right_depth) + 1

# 中序遍历的反面例子，比如如下两棵树
#         __2
#        /
#       1
#       和
#       1__
#          \
#           2
# 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}

# 提交这个类
class Codec:
    def serialize(self, root):
        # 核心思想：使用先序遍历（根-左-右）将树递归地转换成字符串。
        # 空节点用特殊字符'#'表示，节点之间用','分隔。 #叫sharp
        res = [] #res是结果列表result
        self._f(root, res)
        return ",".join(res)

    def _f(self, root, res): # 递归函数求先序遍历
        if not root:
            res.append("#")
            return
        res.append(str(root.val))
        self._f(root.left, res)
        self._f(root.right, res)

    def deserialize(self, data):
        # 核心思想：利用先序遍历的顺序，递归地重建树。
        # 字符串按','分割成列表，然后用一个迭代器顺序消费这些值来构建节点。
        if not data:
            return None
        vals = iter(data.split(','))
        return self._g(vals)

    def _g(self, vals): # 递归函数求反序列化
        val = next(vals) # 迭代器，next是取下一个值，val是理论上是字符串，next能逐个取值
        if val == "#":
            return None
        
        # 先构建根节点，然后递归构建左子树，再递归构建右子树
        head = Code05_PreorderSerializeAndDeserialize.TreeNode(int(val))
        head.left = self._g(vals)
        head.right = self._g(vals)
        return head

# 提交这个类，补点思想即：把所有空节点也序列化/反序列化出来，不遗漏任何节点位置。
# 按层序列化
class Codec:
    def serialize(self, root):
        # 核心思想：使用广度优先搜索（BFS）进行层序遍历。
        # 队列中的每个节点，都将其左右子节点（即使是None）的信息加入结果字符串。
        if not root:
            return ""  # 空树直接返回空字符串
        res = []
        queue = deque([root])
        while queue:
            cur = queue.popleft()
            if cur:
                res.append(str(cur.val))  # 记录当前节点值
                queue.append(cur.left)    # 即使是None也加入队列，补点思想
                queue.append(cur.right)   # 即使是None也加入队列，补点思想
            else:
                res.append("#")  # 用'#'表示空节点，补点思想
        return ",".join(res)  # 用逗号连接成字符串

    def deserialize(self, data):
        # 核心思想：同样使用BFS和队列来重建树。
        # 先创建根节点并入队，然后依次出队父节点，并从字符串值列表中读出左右子节点的信息进行构建和连接。
        if not data:
            return None  # 空字符串返回空树
        nodes = data.split(',') # 字符串按逗号分割成列表
        root = self.generate(nodes[0])  # 构建根节点
        queue = deque([root])
        index = 1  # 指向下一个要处理的节点值在nodes中的位置
        while queue:
            parent = queue.popleft() #这个循环是按层从顶到下遍历的，parent是父节点
            if index < len(nodes):
                # 生成父节点的左孩子，补点思想
                parent.left = self.generate(nodes[index])
                index += 1
            if index < len(nodes):
                # 生成父节点的右孩子，补点思想
                parent.right = self.generate(nodes[index])
                index += 1
            # 只将非空子节点入队
            if parent.left:
                queue.append(parent.left)
            if parent.right:
                queue.append(parent.right)
        return root

    def generate(self, val):
        if val == "#":
            return None  # 空点返回None，补点思想
        return Code06_LevelorderSerializeAndDeserialize.TreeNode(int(val))  # 普通点返回节点对象

# 提交如下的方法
def buildTree(self, pre: List[int], tin: List[int]) -> Optional[TreeNode]:
    if not pre or not tin or len(pre) != len(tin):
        return None
    # 为了快速查找根节点在中序遍历中的位置，预处理成哈希表
    in_map = {val: i for i, val in enumerate(tin)}
    return self._f(pre, 0, len(pre) - 1, tin, 0, len(tin) - 1, in_map) #初始化方法

def _f(self, pre, l1, r1, tin, l2, r2, in_map):
    if l1 > r1:
        return None
    head = self.TreeNode(pre[l1])
    if l1 == r1: # 如果l1和r1相等，说明只有一个节点，直接返回head
        return head
    
    # k是根节点在中序遍历中的位置
    k = in_map[pre[l1]]
    # 左子树的节点数量
    left_size = k - l2
    
    # 递归构建左子树和右子树
    # pre : l1(........)[.......r1] -> l1是根, (l1+1...l1+left_size)是左子树, (...)是右子树
    # in  : (l2......)k[........r2] -> k是根, (l2...k-1)是左子树, [...]是右子树
    head.left = self._f(pre, l1 + 1, l1 + left_size, tin, l2, k - 1, in_map)
    head.right = self._f(pre, l1 + left_size + 1, r1, tin, k + 1, r2, in_map)
    return head

# 提交以下的方法，实际上是一个又一个节点的bfs
def isCompleteTree(self, h: Optional[TreeNode]) -> bool:
    if not h:
        return True
    queue = deque([h])
    # 是否遇到过左右两个孩子不双全的节点
    leaf_stage = False
    while queue:
        node = queue.popleft()
        # case 1: 如果一个节点只有右孩子没有左孩子，必不是完全二叉树
        # case 2: 如果已经遇到了不双全的节点(进入leaf_stage)，后面又出现了孩子节点，也不是完全二叉树
        if (not node.left and node.right) or \
            (leaf_stage and (node.left or node.right)):
            return False
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        
        # 一旦遇到孩子不双全的节点，就进入leaf_stage设为true，下一次循环中进行判断
        if not node.left or not node.right:
            leaf_stage = True
    return True

def countNodes(self, head: Optional[TreeNode]) -> int:
    if not head:
        return 0
    h = self._mostLeft(head, 1)  # 计算整棵树的高度
    return self._f(head, 1, h)

def _f(self, cur, level, h):
    """
    cur: 当前来到的节点
    level: 当前cur来到的节点在第几层
    h: 整棵树的高度
    返回: cur这棵子树上有多少节点
    """
    if level == h: # base case: 遍历到了最底层
        return 1
    
    # 如果右子树的最左路径能到达整棵树的最后一层
    if self._mostLeft(cur.right, level + 1) == h:
        # 说明cur的左子树是满二叉树，其节点数可以直接计算
        # 节点总数 = 左子树节点数(2^(h-level)-1) + 根节点(1) + 递归求右子树节点数
        # 合并后就是 (1 << (h - level)) + 递归求右子树
        return (1 << (h - level)) + self._f(cur.right, level + 1, h) #1 << n 表示将数字1向左移动n位
    else: #if else判断往左递归还是往右递归
        # 否则，说明cur的右子树是比左子树少一层的满二叉树
        # 节点总数 = 右子树节点数(2^(h-level-1)-1) + 根节点(1) + 递归求左子树节点数
        # 合并后就是 (1 << (h - level - 1)) + 递归求左子树
        return (1 << (h - level - 1)) + self._f(cur.left, level + 1, h)

def _mostLeft(self, cur, level):
    """
    当前节点是cur，并且它在level层
    返回从cur开始不停往左，能扎到几层
    """
    while cur:
        level += 1
        cur = cur.left
    return level - 1
    

# 标准BFS模板
queue = deque([root])
while queue:
    size = len(queue)  # 当前层节点数
    for _ in range(size):  # 处理当前层
        node = queue.popleft()
        # 处理当前节点
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 递归模板
def traverse(root):
    if not root:  # base case
        return
    # 处理当前节点
    traverse(root.left)   # 递归左子树
    traverse(root.right)  # 递归右子树

# 根节点编号为1
# 左子节点编号为 2*i
# 右子节点编号为 2*i + 1

# 先序序列化：根-左-右
# 层序序列化：逐层BFS + 补点
# 中序无法唯一确定树结构

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

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        寻找最近公共祖先的核心函数
        采用递归的方式深度优先搜索
        """

        # 遇到空，或者p，或者q，直接返回
        # 这是递归的基准情况 (base case)
        if not root or root == p or root == q: # 如果root不空的话，这样从下往上会一直传p或者q
            return root

        # 在左子树和右子树中递归查找 p 和 q
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

        # 左树也搜到，右树也搜到，返回root
        # 这意味着p和q分别在root的左右两侧，root是它们的LCA
        if l and r:
            return root
        
        # 如果左右子树的搜索结果都为空，说明p,q不在此子树
        if not l and not r:
            return None
        
        # l和r一个为空，一个不为空
        # 返回不空的那个，这个非空节点要么是p或q本身，要么已经是p和q的LCA
        return l if l else r

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        在二叉搜索树(BST)中寻找最近公共祖先
        利用BST的特性，可以高效地进行迭代查找
        """

        # 确定p和q节点值的范围
        min_val = min(p.val, q.val)
        max_val = max(p.val, q.val)

        # 循环遍历，直到找到LCA
        while root:
            # 如果当前节点的值大于p和q的最大值，说明LCA在左子树
            if root.val > max_val:
                root = root.left
            # 如果当前节点的值小于p和q的最小值，说明LCA在右子树
            elif root.val < min_val:
                root = root.right
            # 否则，当前节点的值在[min_val, max_val]之间，它就是LCA
            else:
                return root
        
        return None # 理论上在有效输入下不会到达这里

from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        """
        主函数，初始化结果列表和路径列表，并启动递归搜索
        """
        ans = []
        if root:
            path = []
            # 调用递归辅助函数 f
            self.f(root, targetSum, 0, path, ans) # 一开始sum=0，ans也是空列表，path也是空列表
        return ans

    def f(self, cur: TreeNode, aim: int, current_sum: int, path: List[int], ans: List[List[int]]):
        """
        递归辅助函数，用于深度优先搜索所有路径
        """  

        # 将当前节点值加入路径
        path.append(cur.val) 
        
        # 判断是否为叶节点
        is_leaf = cur.left is None and cur.right is None 
        
        if is_leaf:
            # 叶节点
            # 如果当前路径和加上叶节点的值等于目标值，则找到一个有效路径
            if current_sum + cur.val == aim: 
                # 将路径的副本添加到结果中
                # 必须是副本(path[:])，否则后续的回溯操作会影响已存入的结果
                ans.append(path[:])
        else:
            # 不是叶节点
            # 递归探索左子树
            if cur.left:
                self.f(cur.left, aim, current_sum + cur.val, path, ans)
            # 递归探索右子树
            if cur.right:
                self.f(cur.right, aim, current_sum + cur.val, path, ans)
        
        # 回溯步骤：当一个节点的左右子树都探索完毕后，
        # 将该节点从当前路径中移除，返回到其父节点的递归调用中。
        path.pop() # 用 path.pop() 把刚才加入的那个节点移除，恢复到进入递归前的状态

from typing import Optional

class Solution:
    def __init__(self):
        # balance是实例变量，用于在递归调用中共享状态，所以能够实现全局变量的效果
        # 每次判断开始时，在主函数中将其重置为true
        self.balance = True

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        """
        主函数，用于启动平衡性检查
        """
        # 重置平衡标志
        self.balance = True
        # 调用递归函数计算高度并检查平衡性
        self.height(root)
        return self.balance

    def height(self, cur: Optional[TreeNode]) -> int:
        """
        递归计算节点高度，并在此过程中检查平衡性
        """
        # 核心思想（后序遍历）：
        # 1. 要判断当前节点是否平衡，需要先知道其左右子树的高度。
        # 2. 这天然地符合后序遍历的顺序（先左、再右、后根）。
        # 3. 递归地计算左子树和右子树的高度。
        # 4. 在计算完左右子树高度后，检查它们的高度差。如果差值大于1，说明树不平衡。
        # 5. 使用一个全局或实例变量 `self.balance` 来记录是否已发现不平衡。
        #    一旦发现不平衡，就将此标志设为False，后续的递归调用可以提前终止。

        # 一旦发现不平衡，或者当前节点为空，返回0，后续计算已无意义或到达递归边界
        if not self.balance or cur is None:
            return 0
        
        # 递归计算左子树的高度
        lh = self.height(cur.left)
        # 递归计算右子树的高度
        rh = self.height(cur.right)
        
        # 检查左右子树的高度差
        if abs(lh - rh) > 1:
            # 如果高度差大于1，则标记为不平衡
            self.balance = False
        
        # 返回当前节点的高度，即左右子树中较高者的高度加1
        # 叶子节点的高度为 1，因为它的左右子树高度都是 0，返回 max(0, 0) + 1 = 1
        return max(lh, rh) + 1

def isValidBST1(self, head: Optional[TreeNode]) -> bool:
    """
    通过迭代方式进行中序遍历来验证BST。
    核心思想：
    一个有效的BST，其中序遍历的结果必然是一个严格递增的序列。
    因此，我们可以在遍历过程中，持续比较当前节点的值和前一个节点的值。
    如果发现当前节点值小于或等于前一个节点值，那么它就不是一个BST。
    """
    if not head:
        return True
    
    stack = []
    pre_node = None
    
    # 使用cur指针和栈来模拟递归的中序遍历
    cur = head
    while stack or cur:
        if cur:
            # 一直向左，将路径上的节点入栈
            stack.append(cur)
            cur = cur.left
        else:
            # 左边到头了，从栈中弹出一个节点，这个就是中序遍历的当前节点
            cur = stack.pop()
            
            # 检查中序遍历的有序性，pre_node是当前节点的前一个节点
            if pre_node is not None and pre_node.val >= cur.val:
                return False
            
            # 更新前一个节点，然后转向右子树
            pre_node = cur
            cur = cur.right
            
    return True

def __init__(self):
    # 实例变量，用于在递归调用中传递子树的最小值和最大值
    self.min_val = float('inf')
    self.max_val = float('-inf')

def isValidBST2(self, head: Optional[TreeNode]) -> bool:
    """
    通过递归方式验证BST。
    核心思想：
    对任意一个节点，它必须满足：
    1. 它的左子树是BST，且左子树所有节点的值都小于它自身的值。
    2. 它的右子树是BST，且右子树所有节点的值都大于它自身的值。
    这个过程可以通过后序遍历，在返回时收集子树的信息（是否为BST，最大值，最小值）来完成。
    """
    # Base case是 head is None，即空树的情况，
    if head is None:
        # 基准情况：空树是有效的BST
        # 初始化min和max，确保不影响上层计算
        self.min_val = float('inf')
        self.max_val = float('-inf')
        return True

    # 递归检查左子树是不是有效的BST
    is_left_ok = self.isValidBST2(head.left)
    l_min = self.min_val  # 保存左子树的最小值
    l_max = self.max_val  # 保存左子树的最大值
    
    # 递归检查右子树是不是有效的BST
    is_right_ok = self.isValidBST2(head.right)
    r_min = self.min_val
    r_max = self.max_val
    
    # 更新当前树的min和max值
    self.min_val = min(l_min, r_min, head.val)
    self.max_val = max(l_max, r_max, head.val)
    
    # 综合判断当前节点是否满足BST的条件
    # 1. 左右子树本身都是BST (is_left_ok and is_right_ok)
    # 2. 左子树的最大值必须小于当前节点值 (l_max < head.val)
    # 3. 右子树的最小值必须大于当前节点值 (head.val < r_min)
    return is_left_ok and is_right_ok and l_max < head.val and head.val < r_min