“This is the 14th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

The title

Give you the root node of the binary tree, root, and return the sequential traversal of its node value. (That is, layer by layer, all nodes are accessed from left to right).

Example 1

Input: root = [3,9,20, null, null, 15, 7] output: [[3], [9], [15, 7]]Copy the code

Example 2

Input: root = [1]Copy the code

Example 3

Input: root = [] Output: []Copy the code

Train of thought

Every node of a binary tree has the same structure, so the recursive solution is a good choice.

From the result of example 1, if root has n layers, then ans should have n elements, and each element is an array type, and each element holds the node values accessed in sequence. But the order of recursion is usually DFS (depth-first search), meaning that each node cannot be accessed from left to right in layer order.

Since recursion cannot access nodes in order, we can set an auxiliary value for each node, level, to represent the level of the node; Then, for each node, the entire tree is accessed in the order of first accessing the left subtree, then the right subtree. The root node, which can be regarded as layer 0;

The complete recursion code is shown below

    /** * 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 {number[][]}* /
    var levelOrder = function(root) {
        const ans = [];

        const dfs = (root, level) = > {
            // If the node is empty, end the recursion
            if(! root)return;

            // Initialize the element as []
            if(! ans[level]) { ans[level] = []; }// Put it into the corresponding element according to the hierarchy
            ans[level].push(root.val);

            // Set level + 1 to access the left and right subtrees
            dfs(root.left, level + 1);
            dfs(root.right, level + 1);
        }

        // Access the root node
        dfs(root, 0);

        return ans;
    };
Copy the code

Consider: Is there a way to traverse the tree from left to right, hierarchically?

A good way to do this is to maintain a stack, and first push nodes of a certain level onto the stack. When the stack is complete, the number of elements in the current stack is the number of elements of the current level. At this point, these elements are pushed off the stack in turn, saving the value of the current node and putting the left and right subtrees of the node on the stack. When the stack is not empty, the process continues. When the stack is empty, the tree is traversed and the nodes are accessed from left to right in a hierarchical order.

Breadth-first traversal of complete code

    / * * *@param {TreeNode} root
     * @return {number[][]}* /
    var levelOrder = function(root) {
        const ans = [];

        if(! root) {return ans;
        }
        
        const stack = [];

        // The root node is pushed
        stack.push(root);

        while(stack.length ! =0) {

            // Save the number of nodes in the current tier
            const levelSize = stack.length;
            // Put the initialized data structure first
            ans.push([]);
            for(let i = 0; i < levelSize; i++) {
                // exit the stack
                const node = stack.shift();

                // Access the element value and save
                ans[ans.length - 1].push(node.val);

                // The left and right nodes are pushed
                if(node.left) stack.push(node.left);
                if(node.right) stack.push(node.right); }}return ans;
    };
Copy the code

summary

Depth-first traversal algorithms generally use recursion; Breadth-optimized traversal, on the other hand, generally requires the maintenance of an additional stack to hold the nodes of the current hierarchy. The time complexity of the two traversal methods is generally O(n), that is, each node will be accessed once. For binary tree traversal, both traversal methods need to be mastered.

LeetCode 👉 HOT 100 👉 Sequence traversal of binary trees – medium problem ✅

Collection: LeetCode 👉 HOT 100, will update when you are free, we support a lot, click a like 👍

If you have a good solution or find something wrong with this article, please leave a comment at 😄