leetcode114-二叉树展开为链表

leetcode 114

思路

用简单例子推导规律

不要一开始就看复杂的树，先从最简单的情况入手

案例一：只有一个节点

输入：1
输出：1

不需要任何操作，直接返回

案例二：有两个节点

输入：   1
       /
      2
      
输出：1→2

步骤：

• 把左子树（2）移到右边
• 左子树指针设为 null

案例三：有三个节点

输入：   1
       / \
      2   3
      
输出：1→2→3

步骤：

• 把左子树（2）移到右边
• 找到新右子树（2）的最右节点
• 把原右子树（3）接到最右节点后面

画出转换过程

原树：
    1
   / \
  2   3
  
第一步：移左子树到右边
    1
     \
      2
     / \
null   3

第二步：找到最右节点（2）
    1
     \
      2
       \
        3

第三步：左指针设为null
    1
     \
      2
       \
        3

已经知道如何展开左子树和右子树，如何利用这些结果展开当前树？

分治思想

• 先展开左子树（得到链表 A）
• 再展开右子树（得到链表 B）
• 把链表 A 接到根节点右边
• 找到链表 A 的末尾
• 把链表 B 接到 A 的末尾

const deep = (root) => {
    if (!root) return null;
    // 递归展开左子树
    const left = deep(root.left);
    // 递归展开右子树
    const right = deep(root.right);

    // 处理当前节点：将左子树放到右子树的位置
  };

如何实现 “移左接右” 操作

• 保存原左右子树
• 将左子树移到右子树位置
• 找到新右子树的最右节点
• 将原右子树接到最右节点

if (left) {
     root.right = left;
     root.left = null;

     // 寻找左子树的最右节点
     let cur = root;
     while (cur.right) {
       cur = cur.right;
     }

    // 将右子树连接到左子树的最右节点
    cur.right = right;
 }

实现

var flatten = function (root) {
  const deep = (root) => {
    if (!root) return null;
    // 递归展开左子树
    const left = deep(root.left);
    // 递归展开右子树
    const right = deep(root.right);

    // 处理当前节点：将左子树放到右子树的位置
    if (left) {
      root.right = left;
      root.left = null;

      // 寻找左子树的最右节点
      let cur = root;
      while (cur.right) {
        cur = cur.right;
      }

      // 将右子树连接到左子树的最右节点
      cur.right = right;
    }
    return root;
  };

  return deep(root);
};