上海专业网站建设公司电话智汇隆网站建设

上海专业网站建设公司电话,智汇隆网站建设,wordpress的样式表,凡科登陆【算法详解】如何根据“扩展先序遍历”构建二叉树#xff1f; 在二叉树的算法题中#xff0c;我们常遇到的问题是#xff1a;给定二叉树求遍历序列。但反过来#xff0c;给定一个遍历序列#xff08;字符串#xff09;#xff0c;如何还原出一棵二叉树#xff1f; 通常…【算法详解】如何根据“扩展先序遍历”构建二叉树在二叉树的算法题中我们常遇到的问题是给定二叉树求遍历序列。但反过来给定一个遍历序列字符串如何还原出一棵二叉树通常情况下单靠一个先序遍历是无法唯一确定一棵树的需要先序中序。但是如果输入序列中包含了空指针的信息比如用#表示空节点那么仅凭先序遍历序列就能唯一确定这棵二叉树。今天我们通过一道经典题目TSINGK110来深入剖析这种“扩展先序遍历”的构建逻辑。1. 题目核心分析输入abc##de#g##f###含义这是一个先序遍历根 - 左 - 右。#代表空节点null。非#字符代表真实的节点值。目标构建出这棵树并输出它的中序遍历。2. 核心解题思路递归 全局游标代码采用了最直观也最有效的解法递归构建。因为先序遍历的特性是第一个字符肯定是根节点紧接着是左子树的数据再后面是右子树的数据。但是左子树占了多少个字符右子树从哪里开始我们不知道。这就需要引入一个全局变量i或者叫全局游标。它像一个指针随着递归的进行始终指向字符串中当前待处理的那个字符。哪怕在递归深处大家操作的都是同一个i这样就不会乱。3. 深度拆解createTree方法灵魂所在这是整个代码的核心让我们逐行剖析逻辑publicstaticinti0;// 全局游标publicstaticTreeNodecreateTree(Stringstr){// 1. 获取当前游标指向的字符charchstr.charAt(i);TreeNodenewrootnull;// 2. 判断是否是空节点标记if(ch!#){// 情况 A是真实节点 newrootnewTreeNode(ch);// 创建节点i;// 游标后移准备处理下一个字符// 【关键递归】// 既然我是根那字符串里紧接着我的肯定是我的左子树内容newroot.leftcreateTree(str);// 当左子树全部构建完毕递归返回后// 游标 i 已经跑到了右子树数据的开头newroot.rightcreateTree(str);}else{// 情况 B是空节点 // 不需要创建节点newroot 保持为 nulli;// 游标后移跳过这个 #}// 3. 返回构建好的节点或者 nullreturnnewroot;}图解执行流程以abc##...为例让我们模拟一下计算机的堆栈看createTree是如何“生长”出这棵树的Layer 1: 读入a。创建节点A。i变为 1。调用root.left createTree()。Layer 2: 读入b。创建节点B。i变为 2。调用root.left createTree()。Layer 3: 读入c。创建节点C。i变为 3。调用root.left createTree()。Layer 4: 读入#。ch是#。i变为 4。返回null。(回到 Layer 3C 的左孩子设为 null)Layer 3 继续执行调用root.right createTree()。Layer 4: 读入#。ch是#。i变为 5。返回null。(回到 Layer 3C 的右孩子设为 null)Layer 3 执行完毕返回节点 C。(回到 Layer 2B 的左孩子设为 C)Layer 2: B 的左孩子搞定了继续调用root.right createTree()…总结只要遇到非#我就生孩子只要遇到#我就告诉爸爸“这里没路了null”然后指针继续往后移去处理树的下一部分。4. ⚠️ 易错点修正多组数据的坑这段代码逻辑在处理单组数据时是完美的。但是题目描述中提到“可能有多组测试数据”while (in.hasNextLine()) { ... }该代码存在一个严重的隐患public static int i 0;是定义在类级别的静态变量。场景模拟第一组数据abc##跑完i变成了 5。while循环进入第二轮读入新字符串。再次调用createTree此时i还是 5程序会直接从新字符串的第 5 个字符开始读或者直接抛出StringIndexOutOfBoundsException。修正方案必须在每组测试数据开始处理前手动重置i 0。publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNextLine()){Stringstrin.nextLine();i0;// 【重要】必须在这里重置游标TreeNodeTargetrootcreateTree(str);inOrder(Targetroot);System.out.println();// 建议每组输出后换行方便阅读}}5. 完整代码优化结合以上分析最终完美的代码结构如下importjava.util.Scanner;classTreeNode{publiccharval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(charval){this.valval;}}publicclassMain{// 全局游标用于记录字符串处理到了哪个位置publicstaticinti0;publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);while(in.hasNextLine()){Stringstrin.nextLine();// 【修正】处理新的一行之前必须重置游标i0;TreeNodeTargetrootcreateTree(str);inOrder(Targetroot);System.out.println();// 格式优化换行}}// 核心构建逻辑publicstaticTreeNodecreateTree(Stringstr){// 防止游标越界虽然题目保证输入合法但加上更安全if(istr.length())returnnull;charchstr.charAt(i);i;// 读取一个字符后游标必须后移// 递归出口遇到空节点标记if(ch#){returnnull;}// 递归构建根 - 左 - 右TreeNodenewrootnewTreeNode(ch);newroot.leftcreateTree(str);newroot.rightcreateTree(str);returnnewroot;}// 中序遍历左 - 根 - 右publicstaticvoidinOrder(TreeNoderoot){if(rootnull)return;inOrder(root.left);System.out.print(root.val );inOrder(root.right);}}6. 总结这道题是理解二叉树序列化的基石。思路利用先序遍历的顺序特性根-左-右。技巧使用全局变量i来在递归层级之间“传递”当前的进度。陷阱在多组输入的在线判题系统OJ中永远不要忘记重置全局/静态变量。掌握了这个createTree的写法以后遇到“序列化二叉树”或“反序列化二叉树”的题目你就能信手拈来了