企业官网建设流程全解析

腾讯建设网站视频视频下载,国外网页游戏网站,湖南长沙关键词推广电话,东阳网络推广【牛客BM30】二叉搜索树与双向链表#xff1a;java中以引用代指针操作的艺术与陷阱在数据结构面试中#xff0c;“将二叉搜索树#xff08;BST#xff09;转换成有序的双向链表” 是一道考察指针操作、递归思维以及边界条件处理的经典题目。 题目要求我们在 O(1)O(1)O(1) 空…【牛客BM30】二叉搜索树与双向链表java中以引用代指针操作的艺术与陷阱在数据结构面试中“将二叉搜索树BST转换成有序的双向链表”是一道考察指针操作、递归思维以及边界条件处理的经典题目。题目要求我们在O(1)O(1)O(1)空间复杂度原地操作下完成转换这意味着我们不能创建新节点只能改变原有树节点left和right指针的指向。今天我们就来拆解这个问题的核心思路并复盘一个容易被忽视的“空指针陷阱”。1. 核心思路中序遍历 全局前驱为什么是中序遍历二叉搜索树BST的一个核心性质是其中序遍历左 - 根 - 右的结果是严格递增有序的。题目要求生成的双向链表也是有序的。因此解题的大框架必然是中序遍历。怎么把树变成链表我们需要在遍历的过程中修改节点的指针。树节点的left指针→\rightarrow→双向链表的prev指针。树节点的right指针→\rightarrow→双向链表的next指针。关键变量prev为了将当前节点cur与前一个遍历到的节点连接起来我们需要一个全局变量prev来记录**“在中序遍历中上一个访问完的节点”**。算法流程非常类似中序遍历的递归写法只不过中序遍历是在递归左子树和右子树之间加上System.out.print(“root.val” ;而由图可以看出来这二叉树转的双向链表顺序明显满足中序遍历。递归左子树先处理左边把左边已经转换好。处理当前节点连接操作将当前节点root的左指针指向prev(root.left prev)。如果prev不为空将prev的右指针指向当前节点 (prev.right root)。更新prev当前节点处理完毕它变成了下一个节点的“前驱”所以prev root。递归右子树继续处理右边。2. 代码深度解析publicclassSolution{// 全局变量记录中序遍历过程中“上一个”处理过的节点TreeNodeprevnull;publicTreeNodeConvert(TreeNodepRootOfTree){// 【问题核心】为什么要单独判断空后面会详细解答if(pRootOfTreenull)returnnull;// 1. 执行中序遍历修改指针ConvertChild(pRootOfTree);// 2. 寻找链表头节点// 转换完后pRootOfTree 还在树的根节点位置也就是链表的中间某处// 双向链表的头节点应该是“最左侧”的节点TreeNodeheadpRootOfTree;while(head.left!null){headhead.left;}returnhead;}// 辅助函数标准的中序遍历框架publicvoidConvertChild(TreeNoderoot){if(rootnull)return;// 递归终止条件// 1. 递归左子树ConvertChild(root.left);// 2. 核心连接逻辑root.leftprev;// 当前节点的左指针指向前驱if(prev!null){prev.rightroot;// 前驱的右指针指向当前节点双向绑定}prevroot;// 移动 prev 指针当前节点成为下一个节点的前驱// 3. 递归右子树ConvertChild(root.right);}}3. 灵魂拷问为什么必须在 Convert 中加判空这是本题最容易踩坑的地方。问题描述明明在ConvertChild函数的第一行已经写了if(root null) return;为什么在主函数Convert开头不加if(pRootOfTree null) return null;就会导致部分测试用例空树不通过详细解答这里的判空不是为了防止递归出错而是为了防止后续寻找头节点时的空指针异常。让我们模拟一下输入为空树{}的情况假设没有Convert函数里的判空。输入pRootOfTree为null。调用ConvertChild(null)。进入辅助函数触发if(root null) return;函数直接结束没问题。回到Convert主函数继续往下执行。执行TreeNode head pRootOfTree;此时head被赋值为null。执行while(head.left ! null)。程序试图访问null.left。 崩抛出java.lang.NullPointerException。结论ConvertChild中的判空是递归的终止条件Base Case它保证了递归能正常结束。而Convert中的判空是防御性编程它保护了后续寻找head的逻辑head.left不操作空对象。如果不加这一句当输入是空树时程序会在寻找头节点时崩溃。4. 寻找头节点的两种策略在代码中我们通过while循环往左走来寻找头节点。其实还有一种不需要循环的方法由于prev在遍历结束后会指向链表的尾节点中序遍历的最后一个节点我们可以利用prev一路往左推利用left指针或者记录最开始的head。但在本题的结构下直接从pRootOfTree往左找head是最直观的因为转换后的链表依然保持了left指向更小元素的特性。5. 总结这道题考察了三个核心点理解 BST 性质中序遍历即有序。双指针操作在遍历过程中动态修改left和right像缝衣服一样把节点串起来。鲁棒性处理input null的边界情况避免后续逻辑空指针异常。