LeetCode 二叉树展开为链表

二叉树展开为链表

思考

可以很自然想到的是需要一个递归，因为他需要先序遍历
我们会直接进入到每个左边子树的左节点。
但是这经过的右子树是暂时用不到的，所以需要想办法把他们存起来，在稍后使用

const flatten = (root) => {
  if (root === null) return root;

  const stack = [];
  const dig = (root) => {
    if (root === null) return;
    const right = root.right;
    root.right = null;
    // 暂存右节点
    if (right !== null) stack.push(right);

    // 将左节点放到有节点上
    // 并先序遍历继续递归向下
    if (root.left !== null) {
      root.right = root.left;
      root.left = null;
      dig(root.right);
    } else {
      // 如果已经没有下面的节点
      // 从队列中取出最后的右子树遍历
      const next = stack.pop();
      if (next == undefined) return;
      root.right = next;
      dig(next);
    }
  };
  dig(root);
  return root;
};

还可以思考用 O(1) 的空间复杂度，解决这个问题。既然不能用额外的储存空间，那么可以考虑将用到的信息放在树的节点上操作。

题目要求是以先序遍历的顺序，并且通用右指针相连，对于右指针相连这个问题我们可以弱化它，因为这可以通过节点交换很容易的完成。

而以先序遍历顺序返回，并不意味着一定要先访问根节点，只要处理之后的链表的顺序是先序遍历就可以了，所以对于一个只有三个节点的子树来说，将右节点接在左节点的后面就是先序遍历。

那要如何保证在访问根节点的时候，左右子树都是一个处理好的链表，我们会想到后序遍历，因为在访问某个节点的时候，他的左右子树都已经在后序遍历的代码位置处理成了链表，可以直接拼接。

所以可以写出下面的框架

const dig = (root) => {
  if (root === null) return;
  dig(root.left);
  dig(root.right);

  // 处理左右节点
};

const flatten = (root) => {
  if (root === null) return root;
  dig(root);
  return root;
};

思考一些具体的细节，当一个节点的左节点不存在的时候，可以直接跳过，因为它只有一个右节点的话不需要处理，或者右节点已经处理成一个链表。

而当一个左节点存在的时候，需要能获取到左节点这个链表中的最后一个，才能和右节点相连，最后还需要交换左右节点。

const dig = (root) => {
  if (root === null) return;
  dig(root.left);
  dig(root.right);

  let last = root.left;
  // 左节点不存在，直接返回
  if (last === null) return;

  // 获取最后一个节点
  while (last.right) {
    last = last.right;
  }

  // 交换左右子树
  last.right = root.right;
  root.right = root.left;
  root.left = null;
};

const flatten = (root) => {
  if (root === null) return root;
  dig(root);
  return root;
};

打赏