朝花夕拾

二叉树展开为链表

3 min read

题目描述

给你二叉树的根结点 root，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2： 输入：root = []
输出：[]

示例 3： 输入：root = [0]
输出：[0]

思路&js代码

1、前序遍历（递归）

好理解

var flatten = function(root) {
    const list = [];
    preorderTraversal(root, list);
    const size = list.length;
    for (let i = 1; i < size; i++) {
        const prev = list[i - 1], curr = list[i];
        prev.left = null;
        prev.right = curr;
    }
};
 
const preorderTraversal = (root, list) => {
    if (root != null) {
        list.push(root);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
    }
}

2、前序遍历（迭代）

var flatten = function(root) {
    const list = [];
    const stack = [];
    let node = root;
    while (node !== null || stack.length) {
        while (node !== null) {
            list.push(node);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
    const size = list.length;
    for (let i = 1; i < size; i++) {
        const prev = list[i - 1], curr = list[i];
        prev.left = null;
        prev.right = curr;
    }
};

3、头插法

采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。 为此，要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树，才能实现这个顺序？ 按照右子树 - 左子树 - 根的顺序 DFS 这棵树。 DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。

具体来说：

  1. 如果当前节点为空，返回。
  2. 递归右子树。
  3. 递归左子树。
  4. 把 root.left 置为空。
  5. 头插法，把 root 插在 head 的前面，也就是 root.right=head。
  6. 现在 root 是链表的头节点，把 head 更新为 root。
var flatten = function(root) {
    let head = null;
    function dfs(node) {
        if (node === null) {
            return;
        }
        dfs(node.right);
        dfs(node.left);
        node.left = null;
        node.right = head; // 头插法，相当于链表的 node.next = head
        head = node; // 现在链表头节点是 node
    }
    dfs(root);
};

Graph View