企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文基于 Java-Interview 面试指南仓库中的《算法-二叉树-多叉树中最长的连续序列》文档展开。该文档聚焦于经典面试题「在一棵多叉树中寻找最长连续序列路径」，给出了一份完整的 Java 后序遍历解法。读完本文，你将掌握down/up双向续接的递归套路、代码逐行含义、手算验证方法，以及该题与二叉树版（LeetCode 549）之间的演进关系，可以直接把这份实现迁移到面试白板或本地编译器运行验证。

问题背景：连续序列问题从二叉树到多叉树的演进

原文档在开头给出了两类参考来源：一类是二叉树版（即 LeetCode 549 号题 Binary Tree Longest Consecutive Sequence II），另一类是多叉树版的解法实现。这说明此类题目在面试中的常见升级路径是：先考二叉树版，再要求推广到多叉树版。

在树结构中，「连续序列（consecutive sequence）」指路径上相邻节点的值严格相差 1 的序列，例如2 → 3 → 4 → 5或5 → 4 → 3 → 2。与「二叉树中最长同值路径」「二叉树最大路径和」等题目不同，本题的路径不要求从根出发，也不要求到叶子结束，它可以在任意一个节点处「拐弯」：

• 一段路径从某个后代节点向上（值逐级 +1）走到拐点；
• 再从拐点向下（值逐级 +1）走进另一个分支。

两条子链在拐点拼接后，整条路径上的值构成一个公差为 1 的等差序列，例如2,3,4,5,6,7,8。这正是 LeetCode 549 中inc + dec - 1思路在 K 叉树上的推广：每个节点只需要知道「向上能续接多长」和「向下能续接多长」，二者加 1 就是经过该节点的最长连续序列。

题目定义与节点结构

输入一棵多叉树（K 叉树）的根节点，返回树中最长连续序列路径的节点数。多叉树节点定义如下：

/** * Definition for a multi tree node. * public class MultiTreeNode { * int val; * List<MultiTreeNode> children; * MultiTreeNode(int x) { val = x; } * } */

约束要点：

• 节点值约定为整数，路径相邻节点值差必须为1（不能是 2 或其他差值，否则链断开）；
• 路径必须沿着树的父子边行走，不能跳跃到不相邻的节点；
• 序列允许整体递增、整体递减，或先递增（向上）再递增（向下）的「单峰」形态；
• 空树返回 0，单节点树返回 1。

核心思路：后序遍历 + 双向续接（down/up）

为什么选择后序遍历

连续序列的续接只发生在父子之间。对于任意节点root，它能否把子节点传上来的链再延长一步，只取决于子节点自身的续接能力，而不依赖父节点。因此采用「先处理所有 children、再处理当前节点」的后序遍历，可以让信息自底向上汇聚：

• 每个子节点返回自己的{down, up}；
• 当前节点判断：哪个子节点值等于root.val + 1（可向下续接），哪个子节点值等于root.val - 1（可向上续接）；
• 聚合后刷新全局答案。

helper 返回值的语义

helper(root)返回int[]{down, up}，其中：

注意：down/up记录的是「边数」，因此经过当前节点的完整路径节点数 =down + up + 1（两条链的边数之和，再加上拐点节点自身）。这是理解代码的关键，也解释了为什么最终答案是down + up + 1而不是down + up。

为什么 down 与 up 必然来自不同分支

对一个子节点来说，child.val == root.val + 1与child.val + 1 == root.val两个条件互斥，不可能同时成立。因此聚合出的down链和up链分别来自两个不同子树，拼接后的路径不会重复经过任何节点，是一条合法树路径。若最长路径整体单调（全部递增或全部递减），它会在链的端点节点处被单独的down或up捕获，同样不会漏解。

仓库原文实现

以下是文档中给出的完整解法（原样保留，可直接复制运行）：

public class Solution { /** * @param root the root of k-ary tree * @return the length of the longest consecutive sequence path */ int max = 0; public int longestConsecutive3(MultiTreeNode root) { // Write your code here if (root == null){ return 0; } helper(root); return max; } public int[] helper(MultiTreeNode root) { int up = 0; int down = 0; if (root == null){ return new int[]{down, up}; } for ( MultiTreeNode node : root.children ){ int[] h = helper(node); if (node.val == root.val + 1){ down = Math.max(down, h[0] + 1); } if (node.val + 1 == root.val){ up = Math.max(up, h[1] + 1); } } max = Math.max(max, down + up + 1); return new int[]{down, up}; } }

逐行精读与实现细节

1. 实例变量max而不是返回值传递答案：最长连续序列的拐点可能出现在树中任意位置，未必经过根节点。所以每处理完一个节点就用down + up + 1刷新一次max，最终longestConsecutive3直接返回全局最大值即可。

2. 外层空树保护：root == null直接返回 0，避免对空指针调用helper。

3. helper内的空判断：属于防御性写法——对叶子节点，children遍历为空，up、down保持 0，返回{0, 0}，同时max = Math.max(max, 0 + 0 + 1) = 1，保证单节点树的答案是 1。

4. down的续接逻辑：当node.val == root.val + 1（子节点比当前节点大 1，值朝子树方向递增）时，子节点返回的h[0]是「从子节点继续向下还能接的边数」，当前节点加 1 即可把链延长到自己，即h[0] + 1；对多个满足条件的子节点取最大。

5. up的续接逻辑：当node.val + 1 == root.val（子节点比当前节点小 1，值朝当前节点方向递增）时，子节点返回的h[1]是「向上追溯至子节点的链边数」，同样加 1 延长到当前节点。

6. 索引约定：返回数组{down, up}中下标 0 是down、下标 1 是up，消费时h[0]、h[1]与之严格对应，交换会导致结果错误。

从方法命名看，longestConsecutive3属于「最长连续序列」系列题的第三个版本（前两版对应二叉树场景），本题在其基础上推广到了 K 叉树——这也是面试官常用的追问手法。

手算验证示例

以如下多叉树为例（最长连续序列应为2→3→4→5→6→7→8，共 7 个节点）：

5 / | \ 4 6 9 / | 3 7 / \ 2 8

逐步推导（括号内为helper返回值{down, up}）：

最终longestConsecutive3返回 7，与手推结果一致。注意根节点 5 的down = 3对应子链5→6→7→8（3 条边），up = 3对应子链2→3→4→5（3 条边），拼接后正是完整的 7 节点路径。

复杂度分析与边界情况

• 时间复杂度 O(n)：每个节点恰好被helper访问一次，children 遍历总量等于边数 n-1，整体线性；
• 空间复杂度 O(h)：递归调用栈深度等于树高 h，最坏情况（退化链表状多叉树）为 O(n)；
• 边界情况：
  • 空树返回 0；
  • 单节点树返回 1（叶子分支的max刷新保证）；
  • 所有子节点值都与根节点相差超过 1（链全部断开）时，答案为 1；
  • 只有一个方向的链（整体递增或整体递减）时，答案由该方向上down或up单独贡献，例如链5→6→7→8在节点 5 处给出down=3, up=0，答案为 4。

从多叉树回看二叉树版（LeetCode 549）

二叉树是多叉树在k = 2时的特例，本题解法可直接套回二叉树：把children换成left/right两个分支，其余逻辑完全一致。二叉树版与多叉树版的差别仅在于：

• 二叉树版只需要比较左右两个孩子，代码上通常显式展开；
• 多叉树版用for循环遍历children列表，天然支持任意分支数。

掌握本题的down/up双向续接套路后，可以顺带解决一系列同构问题，例如「二叉树最长交替路径」「二叉树最大路径和」（把「差 1」约束换成「求和」约束即可迁移）。

延伸阅读：本仓库算法系列

该仓库整理了作者在 BAT 等公司面试中被问过的高频算法题（见 README.md），树与递归相关的题目可继续阅读：

• 算法-二叉树-递归-二叉树反转：与本文同为「树 + 后序递归」的经典题，对比两者能更好地理解递归返回值的不同设计（原地交换 vs 向上汇聚信息）；
• 算法-链表-反转链表-链表相加：链表的递归/迭代归并思想；
• 算法-动态规划-连续子数组最大和：一维场景下「连续」问题的 DP 解法，可与树的连续序列形成对比；
• 算法-数组-滑动窗口-最小连续子数组：另一类「连续」约束下的经典算法。

面试中遇到这类题目时，建议先明确三个问题再动手：路径是否必须经过根？方向是否允许拐弯？返回值是节点数还是边数？——确认后，后序遍历 + down/up 双向续接这套模板即可直接复用。

• 文档
• 教程
• 知识库