递归状态合并的核心是依结构定义规则组合子问题解：链表按值串联、二叉树节点相加并挂载子树、多链表分治归并；终止条件划定边界；需防重复计算、剪枝优化，并确保返回值为可组装的完整结构。
递归过程中的状态合并，核心在于“子问题结果如何组合成原问题解”。它不是简单拼接，而是依据问题结构定义明确的合并规则——比如链表按值大小串联、二叉树按节点相加并递归挂载子树、多个有序链表用分治两两归并。
按结构定义合并逻辑
不同数据结构决定不同的合并方式：
- 链表合并：比较头节点值，取较小者作为新链表头，其next由剩余部分递归合并结果填充
- 二叉树合并：当前节点值相加；左子树合并结果挂到新节点left，右子树同理
- 多链表合并（如力扣23题）：不能逐个合并（O(k²n)），而应分治——先两两合并，再合并结果，降低时间复杂度至O(N log k)
终止条件决定合并边界
合并的前提是子问题已解，而终止条件划清了“无需再拆、可直接返回”的边界：
- 单链表为空 → 直接返回另一链表（即“合并结果就是现存链表”）
- 二叉树某节点为null → 返回另一棵树对应位置节点（本质是“继承结构”）
- 分治中区间重合（start == end）→ 直接返回该链表，不再拆分
避免重复计算与冗余状态
递归本身不自动去重，需主动设计策略防止低效合并：
- 记忆化：若相同参数组合可能多次出现（如带约束的树合并），缓存已算结果
- 尾递归改写：当合并只依赖上一层结果且无回溯运算时，可用累积参数代替深层调用栈
- 提前剪枝：例如合并过程中发现某子树全为0，可直接跳过计算，用另一树对应部分替代
返回值即合并态的载体
每次递归调用的返回值，必须承载完整、自洽的局部解：
- 不能只返回值，而要返回能参与上层组装的结构体（如ListNode*、TreeNode*）
- 若需合并后额外信息（如长度、最大值），可封装为结构体或用引用参数传递
- 注意原地修改 vs 新建节点：链表常复用节点，二叉树常新建节点，影响合并后的内存归属和副作用
