LeetCode 114 前序遍历树成链表-一一网

这是我参与更文挑战的第9天，活动详情查看：更文挑战。

题目：114. 二叉树展开为链表

给你二叉树的根结点 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]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

方法一：递归前序遍历

把链表的节点按照前序遍历放在数组中，然后再串成链表。

这里前序遍历使用递归方法。

代码

/**
 * 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 nodeArr = []

    const preOrderTraverse = (node)=>{
        if(node){
            nodeArr.push(node)
            preOrderTraverse(node.left)
            preOrderTraverse(node.right)
        }
    }

    preOrderTraverse(root)

    for (let index = 0,len = nodeArr.length; index < len; index++) {
        const node = nodeArr[index]
        node.left = null
        node.right = nodeArr[index + 1] || null
    }
};
复制代码

方法二：迭代前序遍历

把链表的节点按照前序遍历放在数组中，然后再串成链表。

这里前序遍历使用迭代方法。

迭代遍历比递归遍历难写啊，总是卡住。。

代码

/**
 * 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 nodeArr = []

    const preOrderTraverse = (node)=>{
        const stack = []
        while (node || stack.length) {
            while (node) {
                // 访问根节点
                nodeArr.push(node);
                stack.push(node);
                //访问子节点
                node = node.left;
            }
            node = stack.pop();
            //访问右节点
            node = node.right;
        }
    }

    preOrderTraverse(root)

    for (let index = 0,len = nodeArr.length; index < len; index++) {
        const node = nodeArr[index]
        node.left = null
        node.right = nodeArr[index + 1] || null
    }
};
复制代码

方法三：深刻理解前序遍历，递归组成链表

按照根左右的顺序，先把根节点按照根左右的顺序串起来，再一层层考虑子树也按照同样的方法把子树串起来，这样就可以把整体串起来了。

既然每个节点的逻辑相同，可以考虑用递归，先串联了子树，从而处理完整个树。

代码

/**
 * 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) {
    function helper(node) {
        if(!node) return null
        const l = helper(node.left)
        const r = helper(node.right)

        //按照前序遍历的顺序串联起来：根左右
        if(!l){
            node.right = r
        }else{
            node.right = l
            //找到左子树的最右子节点，串联上r
            let currentNode = l
            while (currentNode.right) {
                currentNode = currentNode.right
            }
            currentNode.right = r
            currentNode.left = null
            node.left = null
        }
        
        return node
    }
    root = helper(root)
};
复制代码

方法四：倒着把树组成链表

这个方法是看大佬的讲解里的第二种方法明白的。

对于每个节点，不断入栈。前序遍历是根左右，因此这里按照右、左、根的顺序进行连接。

代码

/**
 * 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) {

    //上一个节点，默认链表的最后节点指向null
    let last = null

    function backFlattern(node) {
        if(!node) return 
        backFlattern(node.right)
        backFlattern(node.left)

        node.right = last
        node.left = null
        last = node
    }

    backFlattern(root)
};
复制代码