LeetCode114 二叉树展开为链表

• 题目
• 解题
• • 解题一：前序遍历（递归 + 迭代版本）
  • 解题二：前序遍历和展开同步进行
  • 解题三：寻找前驱节点

题目

解题

解题一：前序遍历（递归 + 迭代版本）

递归版本：

// javascript
var flatten = function(root) {
    const list = [];
    const preorderTraversal = (root) => {
        if (root === null) return;
        list.push(root);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    };
    preorderTraversal(root);
    for (let i = 0; i < list.length - 1; i++) {
        list[i].left = null;
        list[i].right = list[i + 1];
    }
};

迭代版本：

// javascript
var flatten = function(root) {
    const list = [], stk = [];
    while (root !== null || stk.length > 0) {
        while (root !== null) {
            list.push(root);
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        root = root.right;
    }
    for (let i = 0; i < list.length - 1; i++) {
        list[i].left = null;
        list[i].right = list[i + 1];
    }
};

解题二：前序遍历和展开同步进行

// javascript
var flatten = function(root) {
    if (root === null) return;
    const stk = [root];
    let prev = null;
    while (stk.length > 0) {
        const curr = stk.pop();
        if (prev !== null) {
            prev.left = null;
            prev.right = curr;
        }
        if (curr.right !== null) stk.push(curr.right);
        if (curr.left !== null) stk.push(curr.left);
        prev = curr;
    }
};

解题三：寻找前驱节点

// javascript
var flatten = function(root) {
    while (root !== null) {
        if (root.left !== null) {
            const next = root.left;
            let predesessor = next;
            while (predesessor.right !== null) {
                predesessor = predesessor.right;
            }
            predesessor.right = root.right;
            root.left = null;
            root.right = next;
        }
        root = root.right;
    }
};