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

preface

Data structure and algorithm belong to the internal work of the developer, no matter how the front-end technology changes, how the framework updates, how the version iteration, it is the same content. Always remember in the byte youth training camp, moon shadow teacher said a word, do not ask front-end learning algorithm. Everyone in computer science needs to know about algorithms and has the subconscious to write high-quality code.

I. Problem description

Given the root node of the binary tree, root, returns a zigzag sequence traversal of its node value. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

Example 1:

Enter: root = [3.9.20.null.null.15.7] Output: [[3], [20.9], [15.7]]
Copy the code

Example 2:

Enter: root = [1] Output: [[1]]
Copy the code

Example 3:

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

 

Tip:

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

Ii. Explanation of ideas

  • The for loop controls the traversal of each layer from left to right
  • Use index to determine the current level, and then determine whether the current is traversed from left to right or right to left
  • Each level holds the array of the corresponding level, and the user stores all the node values of that level, whether from the left or right is the insertion position in the array
  • Return res at the end of the iteration
var zigzagLevelOrder = function(root) {
    const res = []
    const rec = (root,index) = >{
        if(! root)return
        if(! res[index]){ res[index] = [] }if(index%2= =0) {// 0 2 4 from left to right
         res[index].push(root.val)
       }else{ // 1, 3, 5 from right to left
           res[index].unshift(root.val)
       }
        rec(root.left,index+1)
        rec(root.right,index+1)
    }
    rec(root,0)
    return res
};
Copy the code

subsequent

  • Address: Serrated sequence traversal of binary tree

Ok, this article force buckle – binary tree zigzag sequence traversal ends here, MY name is Shao Xiaobai, a junior student in the front-end field, welcome to 👍 comments.