LeetCode 114. 二叉树展开为链表 — Kotlin 实现题目要求将二叉树原地展开为单链表顺序为先序遍历顺序用right指针充当链表的next。思路一迭代推荐O(1)O(1)O(1)额外空间对当前节点若存在左子树找到左子树的最右节点将右子树挂到它后面再把左子树移到右边/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */classSolution{funflatten(root:TreeNode?):Unit{varcurrrootwhile(curr!null){if(curr.left!null){// 找到左子树的最右节点varpredecessorcurr.leftwhile(predecessor?.right!null){predecessorpredecessor.right}// 右子树接到左子树最右节点之后predecessor?.rightcurr.right// 左子树移到右边左指针清空curr.rightcurr.left curr.leftnull}// 移动到下一个节点currcurr.right}}}时间复杂度O(n)空间复杂度O(1)无递归栈思路二递归反向先序遍历按 右 → 左 → 根 的顺序处理把每个节点逐个接到前驱节点的右边classSolution{privatevarprev:TreeNode?nullfunflatten(root:TreeNode?):Unit{if(rootnull)returnflatten(root.right)// 先处理右子树flatten(root.left)// 再处理左子树root.rightprev// 接到已处理好的链表头部root.leftnullprevroot}}时间复杂度O(n)空间复杂度O(h)递归栈深度思路三栈模拟先序遍历迭代直观版用栈按根 → 左 → 右的顺序处理逐个拼接importjava.util.ArrayDequeclassSolution{funflatten(root:TreeNode?):Unit{if(rootnull)returnvalstackArrayDequeTreeNode()stack.push(root)vartail:TreeNode?nullwhile(stack.isNotEmpty()){valnodestack.pop()tail?.apply{rightnode leftnull}tailnode node.right?.let{stack.push(it)}node.left?.let{stack.push(it)}}}}时间复杂度O(n)空间复杂度O(n)Kotlin 实现要点可空类型安全Kotlin 的空安全检查天然契合树节点的可空结构?.和?:让空判断非常简洁。迭代法无递归栈开销Rust/Kotlin 这类语言写迭代版反而比递归更省心避免了成员变量或闭包共享状态。思路二的顺序必须是 右 → 左 → 根先序的逆序prev从null开始逐渐拼出完整链表。示例[1,2,5,3,4,null,6]展开为1 → 2 → 3 → 4 → 5 → 6✅
