I. Title Description:

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20,null,null,15,7],

   3
  /  \
 9   20
    /  \
   15   7
Copy the code

Return the sequence traversal result:

[[3], [9,20], [15,7]

Quote: leetcode-cn.com/problems/bi…

102. Sequential traversal of binary trees

Ii. Analysis of Ideas:

Order traversal of binary trees is similar to breadth-first traversal, except that breadth-first traversal gives us an array.

In order traversal, we need to display the results of breadth-first traversal hierarchically.

  1. We can create an array levelArr that records the number of levels in the binary tree;

  2. Add the root node to levelArr when the root node is not empty;

  3. While loop over levelArr, remember the number of levelArr levelSize; LevelSize specifies the number of tree nodes at the current level. Declare and initialize tempArr to record the value of the tree nodes at the current level. TempArr is used to separate data at each level.

  4. The for loop traverses the left and right subtrees of the level, updating nodes in levelArr as it traverses. (Including removing the first node of levelArr and adding new nodes to levelArr)

  5. After the for loop ends, add tempArr to resultArr;

  6. Return resultArr.

Iii. AC Code:

class Solution {
    func levelOrder(_ root: TreeNode?).- > [[Int]] {
        var resultArr : [[Int]] = [[Int]] ();if (root = = nil) {
            / / empty tree
            return resultArr;
        }
        
        // Record the node array levelArr for each level
        var levelArr : [TreeNode? ]= [TreeNode? ] (a); levelArr.append(root);while (levelArr.count > 0) {
            var tempArr : [Int] = [Int] ();let levelSize = levelArr.count;
            // Traverses the left and right subtrees of the current layer
            for _ in 0..<levelSize {
                // The first element added to the array is left, so remove the element from the front
                let node : TreeNode? = levelArr.removeFirst();
                tempArr.append(node?.val ?? 0);
                if (node?.left ! = nil) {
                    levelArr.append(node?.left);
                }
                if (node?.right ! = nil) {
                    levelArr.append(node?.right);
                }
            }
            resultArr.append(tempArr);
        }
        returnresultArr; }}Copy the code

4. Refer to the learning website

Binary tree

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign