Their thinking

The sequence traversal of binary tree generally adopts the iterative method, and the solution idea is relatively fixed. The basic logical framework is as follows:

  • By queue (fifO)
  • Initial: The root node is queued
  • Start of iteration:

    The nodes in the current queue are removed from the queue in sequence. After each node is removed from the queue, the following requirements are required:
    • If the left child of the current node exists, the left child is enqueued
    • If the right child of the current node exists, the right child is enqueued

    Iterates until the queue is empty, indicating that the entire tree is traversed. In the iteration process, some auxiliary variables can be set according to the actual situation of the topic to save the traversal results.

Code routines

The solution idea is relatively fixed, which means that the code logic of binary tree traversal is relatively fixed. The basic structure of the code is as follows :(the code in this paper uses JavaScript)

  • Iterative method
/ /... // Call a variable to hold the final result const result = []; Const queue = [root]; // Create a queue, assist traversal, and initialize the root of the binary tree While (queue.length > 0) {// Note: // It is recommended to use a temporary variable to record the length of the queue, since arrays are used in JavaScript to simulate queues. Const qLength = queue.length; // Const qLength = queue.length; for (let i = 0; i < qLength; i++) { const currentNode = queue.shift(); Currentnode.left && queue. Push (currentNode.left); currentNode.right && queue.push(currentNode.right); } / /... } / /...Copy the code

LeetCode exercises

  • 102. Sequence traversal of binary trees

    • Iterative method
    /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if (! root) { return []; } const result = []; const queue = [root]; while(queue.length > 0) { const sub = []; const qLength = queue.length; for (let i = 0; i < qLength; i++) { const currentNode = queue.shift(); sub.push(currentNode.val); currentNode.left && queue.push(currentNode.left); currentNode.right && queue.push(currentNode.right); } result.push(sub); } return result; };Copy the code

    • 103. Serrated sequence traversal for binary trees

    • 107. Sequence traversal of binary trees II

    • 199. Right view of binary trees