前端算法题解leetcode114二叉树展开为链表

关于前端算法题解leetcode114二叉树展开为链表，我给出完整的攻略如下：

问题概述

给定一个二叉树，原地将它展开为一个单链表。其中，展开后的单链表应该符合如下要求：

1. 单链表的右节点指针为原先的二叉树中序遍历的后继节点。
2. 单链表的左节点应该为空（因为右节点指针已经代替了左右子树指针）。

例如，给定如下二叉树：

    1
   / \
  2   5
 / \   \
3   4   6

将其展开后，应该获得这样的一条单链表：1 -> 2 -> 3 -> 4 -> 5 -> 6

解决方案

解决这个问题主要考虑两个方面：如何遍历二叉树以及构建链表。

第一个问题得益于递归的思想。我们可以首先将二叉树的左子树展开为单链表，然后将右子树展开为单链表，最后将左子树展开后构成的单链表插入到根节点和右子树单链表之中。这样的递归思路可以用代码实现，起始节点为根节点时，代码如下：

const flatten = function(root) {
  // 如果根节点为空，则返回空链表
  if (!root) return null;

  // 递归展开左子树和右子树
  const left = flatten(root.left);
  const right = flatten(root.right);

  // 将左子树链表插入到根节点和右子树链表之间
  if (left !== null) {
    let p = left;
    while (p.right !== null) {
      p = p.right;
    }
    p.right = right;
    root.right = left;
    root.left = null;
  } else {
    root.right = right;
  }
  return root;
};

第二个问题需要在递归过程中完成。我们需要构建一个新的链表，并且在递归向下走时，将当前节点插入到链表的末尾。这就需要构建链表，在每个节点中保存链表的尾节点，将当前节点插入到尾部。

这样的方法需要考虑的细节较多，实现起来会显得较为繁琐，可以通过代码注释来帮助理解。

示例说明

为了帮助理解，以下分别给出对于二叉树[1,2,5,3,4,null,6]和[1,2,3,null,null,4,null,null,5]的解决过程。

示例一：[1,2,5,3,4,null,6]

1. 根节点为节点1。

• 递归展开左子树和右子树。
• 左子树为节点2。递归展开左子树和右子树。左子树为节点3，构建链表：
• tail = 3
• 3 -> null
• 右子树为节点5。递归展开左子树和右子树。左子树为节点6，构建链表：
• tail = 6
• 6 -> null
• 将左右子树链表插入到父节点1与右子树之间：

 1 -> 2 -> 3 -> null

• 将根节点赋值为当前 tail 节点

 1 -> 2 -> 3 -> null
          |
          1

2. 根节点为节点2。

• 递归展开左子树和右子树。
• 左子树为节点3。递归展开左子树和右子树。左子树为空：
• tail = 3
• 3 -> null
• 右子树为节点4。递归展开左子树和右子树。左子树为空，构建链表：
• tail = 4
• 4 -> null
• 将左右子树链表插入到父节点2与右子树之间：

 1 -> 2 -> 3 -> null
             |
 5 -> 4 -> null

• 将根节点赋值为当前 tail 节点

 1 -> 2 -> 3 -> null
             |
 5 -> 4 -> null
          |
          2

3. 根节点为节点5。

• 递归展开左子树和右子树。
• 左子树为空。
• 右子树为节点6。递归展开左子树和右子树。左子树为空：
• tail = 6
• 6 -> null
• 将左右子树链表插入到父节点5与右子树之间：

 1 -> 2 -> 3 -> null
             |
 5 -> 4 -> null
             |
             6

• 将根节点赋值为当前 tail 节点

 1 -> 2 -> 3 -> null
             |
 5 -> 4 -> null
             |
             6
          |
          1

4. 完成展开，返回 root 节点。

• 将链表输出为字符串形式

 1 -> 2 -> 3 -> 4 -> 5 -> 6

示例二：[1,2,3,null,null,4,null,null,5]

该示例跟上一个示例类似，这里不给出详细解释，只展示最后的链表结果。

 1 -> 2 -> 3 -> 4 -> 5