二叉树展开为链表 2022-03-03 周四

题目

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

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

官方解法

思路

• 前序遍历，将二叉树放入一个数组；先访问元素，然后递归访问左子树，右子树

• 遍历数组，修改元素的指针信息；

JS代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    // 利用前序遍历，将二叉树转化为数组
    const list = [];
    preorderTraversal(root, list);

    // 遍历数组，修改指针信息
    for (let i=1; i<list.length; i++) {
        let previous = list[i-1];
        let current = list[i];

        previous.left = null;
        previous.right = current;
    }

};

// 前序遍历
const preorderTraversal = (root, list) => {
    // 递归退出条件：二叉树没有成员了；
    if (!root) {
        return;
    }

    // 先取元素
    list.push(root);

    // 递归访问左子树
    preorderTraversal(root.left, list);

    // 递归访问左子树
    preorderTraversal(root.right, list);
}