LeetCode 114. 二叉树展开为链表 — Rust 实现题目要求将二叉树原地展开为单链表顺序为先序遍历顺序用right指针充当链表的next。思路一迭代推荐O(1)O(1)O(1)额外空间Rust 的所有权模型处理递归改树比较繁琐迭代法反而是最顺手的写法对当前节点若存在左子树找到左子树的最右节点将右子树挂到它后面再把左子树移到右边。usestd::rc::Rc;usestd::cell::RefCell;implSolution{pubfnflatten(root:mutOptionRcRefCellTreeNode){letmutcurrroot.clone();whileletSome(node)curr{let(mutleft,right){letmutbnode.borrow_mut();(b.left.take(),b.right.take())};ifleft.is_some(){// 找到左子树的最右节点letmutpredleft.clone();loop{letnextpred.as_ref().unwrap().borrow().right.clone();matchnext{Some(r)predSome(r),Nonebreak,}}// 将右子树接到左子树最右节点之后pred.unwrap().borrow_mut().rightright;// 左子树移到右边node.borrow_mut().rightleft;}else{node.borrow_mut().rightright;}// 移动到下一个节点currnode.borrow().right.clone();}}}时间复杂度O(n)空间复杂度O(1)无递归栈思路二递归反向先序遍历利用先序的逆序右 → 左 → 根用共享可变状态记录前驱节点usestd::rc::Rc;usestd::cell::RefCell;implSolution{pubfnflatten(root:mutOptionRcRefCellTreeNode){fndfs(node:OptionRcRefCellTreeNode,prev:mutOptionRcRefCellTreeNode){ifletSome(n)node{let(left,right){letmutbn.borrow_mut();(b.left.take(),b.right.take())};dfs(right,prev);// 先处理右子树dfs(left,prev);// 再处理左子树letmutbn.borrow_mut();b.rightprev.take();// 接到已处理好的链表头部b.leftNone;*prevSome(n.clone());}}letmutprevNone;dfs(root,mutprev);}}时间复杂度O(n)空间复杂度O(h)递归栈深度Rust 实现要点RefCell 双规则borrow_mut()拿写引用前确保之前借用已释放上面的代码都用块作用域let (left, right) { ... }及时释放否则运行时会 panicalready mutably borrowed。take()技巧b.left.take()把字段取出并留下None避免手动mem::replace是 Rust 树操作的标准手法。Rc 共享所有权 LeetCode 的 Rust 树节点是RcRefCellTreeNode克隆Rc只是增加引用计数是廉价操作。不要边borrow_mut边递归递归调用可能再次访问同一节点造成双重借用所以先取出子树释放借用再递归——上面两个写法都遵循这个模式。示例[1,2,5,3,4,null,6]展开为1 → 2 → 3 → 4 → 5 → 6✅
