429. Sequence traversal of N fork tree

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

Given an n-tree, return a sequential traversal of its node values. (that is, from left to right, layer by layer).

The serialized input to the tree is traversed in order, with each set of child nodes separated by null values (see example).

Example 1:

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

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: [[1], [2, 5-tetrafluorobenzoic],,7,8,9,10 [6], [11], [14]]

Specific topic links: topic links

Ideas:

This problem is still a template problem, but there are multiple children on the same node. The binary tree uses the left and right nodes, and this iterates through every node in the childre array, using a for loop that iterates through subscripts. Note the difference between I and children[I]

Analysis:

1. if(! root)return []; // Determine the recursive termination condition

3. Let hash = {}// define hash array let res = []; 4. One of the difficulties of binary tree questions is how to break down the requirements of the questions into what each node needs to do. Function TreeNode(val, left, right) {this.val = (val===undefined? 0 : val) this.left = (left===undefined ? null : left) this.right = (right===undefined ? Null: right)} 6 Loop arguments to recursive functions: Do not use root, which is confusing, use cur 7. Write recursive code step termination condition boundary value define desired variable selection traversal mode (front, middle, back) Recursion (note some variable value changes) return to the question’s request 8. The type of the value returned by the termination condition must be the same as that returned by the function :return root or an additional array res:return []

Code:

var levelOrder = function(root) {
    if(! root)return [];
    let qu = [];
    let res = [];
    qu.push(root);
    while(qu.length) {
        let len = qu.length;
        let link = [];
        for(let i =0; i<len; i++) {let p = qu.shift();
            link.push(p.val);
            // The binary tree uses the left and right nodes, while the for loop traverses every node of the childre array. The for loop traverses the subscript
            for(let i=0; i<p.children.length; i++) {if(p.children[i]) qu.push(p.children[i]);
            }
        }
        res.push([...link]);
    }
    return res;
};
Copy the code

Conclusion:

This is the algorithm series article “binary tree” related problem solution