“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

preface

The sequence traversal of the binary tree in question 102 is shown as follows:

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]Copy the code

A, thinking

Return the result of sequence traversal

Since we want to get results from left to right by the depth of the tree (the number of layers), we need at least one piece of information: how many nodes there are at the current level. The current number of nodes is determined by the previous nodes.

Therefore, when traversing the current node, we need to add the left and right children that are not null to the next-level node nextLevel, which will be provided for the next traversal.

To sum up, there are only two steps to implement:

  1. Iterate over the nodes of the current layer, add the node value to the result set of the current layer, and make each node in turn not emptyLeft the child 和 The right childJoins nodes at the next level
  2. Repeat the first step as long as the nodes in the next layer are not empty

For example

We can use recursion or traversal here, both of which are shown in the implementation code. Here we use recursion as an example:

Some variables are described as follows: List
currentLevel: non-empty nodes of the current layer List
nextLevel: non-empty nodes of the next layer List

Temp: result set of the current layer

Take [3,9,20,null,null,15,7] as an example

  1. The root node is not empty, traversing the first tier nodecurrentLevel = [3], the result set can be obtainedtemp = [3], and then add the left and right children to the next nodenextLevel = [9, 20]
  2. Walk through the second layercurrentLevel = [9, 20], the result set can be obtainedtemp = [9, 20]And then add their left and right children to the next nodenextLevel = [15, 7]
  3. Traverse the third layercurrentLevel = [15, 7], the node set can be obtainedtemp = [15, 7]. There are no left and right children in the current layer node, so the traversal is finished
  4. Returns the resultret = [[3], [9, 20], [15, 7]]Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea, recursion and traversal are two ways to achieve the following

recursive

List<List<Integer>> ret = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    if(root! =null) {
        dfs(Collections.singletonList(root));
    }
    return ret;
}

public void dfs(List<TreeNode> currentLevel) {
    if (currentLevel.size() < 1)
        return;
    List<Integer> temp = new ArrayList<>();
    List<TreeNode> nextLevel = new ArrayList<>();
    // Iterate over the current hierarchy
    for (TreeNode treeNode : currentLevel){
        temp.add(treeNode.val);
        if(treeNode.left ! =null){
            nextLevel.add(treeNode.left);
        }
        if(treeNode.right ! =null){
            nextLevel.add(treeNode.right);
        }
    }
    ret.add(temp);
    dfs(nextLevel);
}
Copy the code

traverse

public List<List<Integer>> levelOrder1(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    if (root == null) {
        return ret;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(! queue.isEmpty()) { List<Integer> temp =new ArrayList<>();
        int currentLevelSize = queue.size();
        for (int i = 1; i <= currentLevelSize; ++i) {
            TreeNode node = queue.poll();
            temp.add(node.val);
            if(node.left ! =null) {
                queue.add(node.left);
            }
            if(node.right ! =null) {
                queue.add(node.right);
            }
        }
        ret.add(temp);
    }
    return ret;
}
Copy the code

The test code

public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(3.new TreeNode(9),
            new TreeNode(20.new TreeNode(15), new TreeNode(7)));
    new Number102().levelOrder(treeNode);
}
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section