跳到主要内容

展开为链表

题目要求把二叉树展开成什么？​

  • 要求: 原址展开成单链表, 节点顺序与前序遍历一致, 所有节点只使用 right 指针;
  • 限制: 必须原地修改, 不额外分配节点;

借助前序数组的做法为什么不够好？​

  • 做法: 先前序遍历收集节点, 再依次串成右链;
  • 代价: 额外占用 O(n) 空间, 不满足原地要求;

如何原地展开？​

  • 思路: 对每个有左子树的节点, 先找到左子树的最右节点, 把原来的右子树挂到它后面, 再把左子树整体搬到右边;
  • 推进: 处理完当前节点后移动到新的右子节点, 直到为空;
  • 复杂度: 时间 O(n) (内层寻找最右节点的工作量被摊还), 空间 O(1);
const flatten = function (root) {
  let node = root;
  while (node != null) {
    if (node.left == null) {
      node = node.right;
      continue;
    }
    let last = node.left;
    while (last.right != null) last = last.right;
    last.right = node.right;
    node.right = node.left;
    node.left = null;
    node = node.right;
  }
};