LeetCode 114 traverses the tree into a linked list

This is the 9th day of my participation in Gwen Challenge.

Title: 114. Binary tree expanded to a linked list

The root of the binary tree is root. Expand it into a single linked list:

The expanded list should also use TreeNode, with the right child pointing to the next node in the list and the left child always null. The expanded list should be traversed in the same order as the binary tree.

Example 1:

Input: root = [6],2,5,3,4 1, null, output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [0] Output: [0]

Tip:

The number of nodes in the tree is in the range [0, 2000] -100 <= node. val <= 100

Method 1: recursive traversal

The nodes of the linked list are traversed through the array in the preceding order, and then connected to the list.

Here the preorder traversal uses a recursive method.

code

/** * 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}};Copy the code

Method 2: sequence traversal before iteration

The nodes of the linked list are traversed through the array in the preceding order, and then connected to the list.

Here the sequential traversal uses the iterative method.

Iterative traversal is harder to write than recursive traversal. It always gets stuck.

code

/** * 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) {
                // Access the root node
                nodeArr.push(node);
                stack.push(node);
                // Access the child node
                node = node.left;
            }
            node = stack.pop();
            // Access the right node
            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}};Copy the code

Method three: deep understanding of the preceding order traversal, recursive composition of the linked list

If you want to string the root nodes in the same order as the root nodes, and then you want to string the subtrees in the same way, then you can string the whole thing together.

Since the logic of each node is the same, consider recursion by concatenating the subtrees first to process the entire tree.

code

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

        // Follow the sequence of previous traversals: root left and right
        if(! l){ node.right = r }else{
            node.right = l
            // Find the rightmost child of the left subtree
            let currentNode = l
            while (currentNode.right) {
                currentNode = currentNode.right
            }
            currentNode.right = r
            currentNode.left = null
            node.left = null
        }
        
        return node
    }
    root = helper(root)
};
Copy the code

Method 4: Form a linked list of trees backwards

This method is to see the second method in the big guy’s explanation to understand.

For each node, it keeps pushing. Front-order traversal is root left and right, so join in right, left, root order.

code

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

    // The last node of the default list points to 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)
};
Copy the code

The resources

Leetcode-cn.com/problems/fl…