.jpg)
621 字
3 分钟
二叉树展开为链表
题目描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
解题思路
- 后序遍历递归法：
- 递归展开左子树，返回左子树尾节点
- 递归展开右子树，返回右子树尾节点
- 将左子树插入根节点与右子树之间
- 左指针置空，返回最终尾节点
- 迭代前驱法：
- 当前节点左子树非空时：
- 寻找左子树最右节点（前驱）
- 前驱节点右指针指向当前节点右子树
- 当前节点右指针指向左子树
- 左指针置空
- 移动到右子树继续处理
- 当前节点左子树非空时：
关键洞察
- 前驱节点作用：
- 左子树的最右节点是右子树的前驱
- 连接前驱与右子树保持前序遍历顺序
- 链表化本质：
- 右指针作为链表 next 指针
- 左指针必须置空
- 就地修改技巧：
- 利用原树指针完成重组
- 无需额外空间存储节点
- 操作顺序关键：
- 必须先处理前驱再修改指针
- 避免丢失子树引用
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归法 | O(n) | O(h) [树高, 最坏O(n)] |
| 迭代前驱法 | O(n) | O(1) |
代码实现
递归法
const flatten = (root) => { const dfs = (node) => { if (!node) return null;
// 叶子节点直接返回 if (!node.left && !node.right) return node;
// 递归处理子树 const leftTail = dfs(node.left); const rightTail = dfs(node.right);
// 重组链表 if (leftTail) { leftTail.right = node.right; node.right = node.left; node.left = null; }
// 返回最终尾节点 return rightTail || leftTail; };
dfs(root);};迭代前驱法
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */var flatten = function (root) { let curr = root; while (curr) { if (curr.left) { // 找到左子树的最右节点 let predecessor = curr.left; while (predecessor.right) { predecessor = predecessor.right; }
// 将右子树接到最右节点 predecessor.right = curr.right;
// 移动左子树到右子树 curr.right = curr.left; curr.left = null; } // 移动到下一个节点 curr = curr.right; }};