【码道初阶】牛客TSINGK110：二叉树遍历（较难）如何根据“扩展先序遍历”构建二叉树？

【算法详解】如何根据“扩展先序遍历”构建二叉树？

在二叉树的算法题中，我们常遇到的问题是：给定二叉树求遍历序列。但反过来，给定一个遍历序列（字符串），如何还原出一棵二叉树？

通常情况下，单靠一个先序遍历是无法唯一确定一棵树的（需要先序+中序）。但是，如果输入序列中包含了空指针的信息（比如用#表示空节点），那么仅凭先序遍历序列，就能唯一确定这棵二叉树。

今天我们通过一道经典题目（TSINGK110），来深入剖析这种“扩展先序遍历”的构建逻辑。

1. 题目核心分析

输入：abc##de#g##f###
含义：

• 这是一个先序遍历（根 -> 左 -> 右）。
• #代表空节点（null）。
• 非#字符代表真实的节点值。

目标：构建出这棵树，并输出它的中序遍历。

2. 核心解题思路：递归 + 全局游标

代码采用了最直观也最有效的解法：递归构建。

因为先序遍历的特性是：第一个字符肯定是根节点，紧接着是左子树的数据，再后面是右子树的数据。

但是，左子树占了多少个字符？右子树从哪里开始？我们不知道。
这就需要引入一个全局变量i（或者叫全局游标）。它像一个指针，随着递归的进行，始终指向字符串中当前待处理的那个字符。哪怕在递归深处，大家操作的都是同一个i，这样就不会乱。

3. 深度拆解createTree方法（灵魂所在）

这是整个代码的核心，让我们逐行剖析逻辑：

publicstaticinti=0;// 全局游标publicstaticTreeNodecreateTree(Stringstr){// 1. 获取当前游标指向的字符charch=str.charAt(i);TreeNodenewroot=null;// 2. 判断是否是空节点标记if(ch!='#'){// === 情况 A：是真实节点 ===newroot=newTreeNode(ch);// 创建节点i++;// 游标后移，准备处理下一个字符// 【关键递归】// 既然我是根，那字符串里紧接着我的，肯定是我的左子树内容newroot.left=createTree(str);// 当左子树全部构建完毕（递归返回）后，// 游标 i 已经跑到了右子树数据的开头newroot.right=createTree(str);}else{// === 情况 B：是空节点 ===// 不需要创建节点，newroot 保持为 nulli++;// 游标后移，跳过这个 '#'}// 3. 返回构建好的节点（或者 null）returnnewroot;}

图解执行流程（以abc##...为例）

让我们模拟一下计算机的堆栈，看createTree是如何“生长”出这棵树的：

1. Layer 1: 读入a。创建节点A。i变为 1。
   • 调用root.left = createTree()。
2. Layer 2: 读入b。创建节点B。i变为 2。
   • 调用root.left = createTree()。
3. Layer 3: 读入c。创建节点C。i变为 3。
   • 调用root.left = createTree()。
4. Layer 4: 读入#。ch是#。
   • i变为 4。返回null。
   • (回到 Layer 3，C 的左孩子设为 null)
   • Layer 3 继续执行，调用root.right = createTree()。
5. Layer 4: 读入#。ch是#。
   • i变为 5。返回null。
   • (回到 Layer 3，C 的右孩子设为 null)
   • Layer 3 执行完毕，返回节点 C。
   • (回到 Layer 2，B 的左孩子设为 C)
6. Layer 2: B 的左孩子搞定了，继续调用root.right = createTree()…

总结：只要遇到非#，我就生孩子；只要遇到#，我就告诉爸爸“这里没路了（null）”，然后指针继续往后移，去处理树的下一部分。

4. ⚠️ 易错点修正（多组数据的坑）

这段代码逻辑在处理单组数据时是完美的。但是题目描述中提到：

“可能有多组测试数据”
while (in.hasNextLine()) { ... }

该代码存在一个严重的隐患：public static int i = 0;是定义在类级别的静态变量。

场景模拟：

1. 第一组数据abc##跑完，i变成了 5。
2. while循环进入第二轮，读入新字符串。
3. 再次调用createTree，此时i还是 5！
4. 程序会直接从新字符串的第 5 个字符开始读，或者直接抛出StringIndexOutOfBoundsException。

修正方案：
必须在每组测试数据开始处理前，手动重置i = 0。

publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);while(in.hasNextLine()){Stringstr=in.nextLine();i=0;// 【重要】必须在这里重置游标！TreeNodeTargetroot=createTree(str);inOrder(Targetroot);System.out.println();// 建议每组输出后换行，方便阅读}}

5. 完整代码优化

结合以上分析，最终完美的代码结构如下：

importjava.util.Scanner;classTreeNode{publiccharval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(charval){this.val=val;}}publicclassMain{// 全局游标，用于记录字符串处理到了哪个位置publicstaticinti=0;publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);while(in.hasNextLine()){Stringstr=in.nextLine();// 【修正】处理新的一行之前，必须重置游标i=0;TreeNodeTargetroot=createTree(str);inOrder(Targetroot);System.out.println();// 格式优化：换行}}// 核心构建逻辑publicstaticTreeNodecreateTree(Stringstr){// 防止游标越界（虽然题目保证输入合法，但加上更安全）if(i>=str.length())returnnull;charch=str.charAt(i);i++;// 读取一个字符后，游标必须后移// 递归出口：遇到空节点标记if(ch=='#'){returnnull;}// 递归构建：根 -> 左 -> 右TreeNodenewroot=newTreeNode(ch);newroot.left=createTree(str);newroot.right=createTree(str);returnnewroot;}// 中序遍历：左 -> 根 -> 右publicstaticvoidinOrder(TreeNoderoot){if(root==null)return;inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}}

6. 总结

这道题是理解二叉树序列化的基石。

• 思路：利用先序遍历的顺序特性（根-左-右）。
• 技巧：使用全局变量i来在递归层级之间“传递”当前的进度。
• 陷阱：在多组输入的在线判题系统（OJ）中，永远不要忘记重置全局/静态变量。

掌握了这个createTree的写法，以后遇到“序列化二叉树”或“反序列化二叉树”的题目，你就能信手拈来了！