This is the 21st day of my participation in Gwen Challenge

Sequence Traversal of binary tree (102)

Topic describes

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).

Advanced:

Recursion is easy. Can you do it iteratively?

Example 1:

Binary tree: [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7Copy the code

Return the sequence traversal result:

[[3], [9,20], [15,7]Copy the code

Thought analysis

The order traversal of binary tree is also a very important knowledge point. In addition to the pre-order, mid-order and post-order (the writing method of recursion and iteration must be mastered), we also need to master the order traversal. Through a queue, each time the size of the queue is recorded, and then traversal these times. So every time we do a while loop, we’re just going to iterate over the number of nodes at one level, and then we’re going to add all the children of that node in turn.

The code shown

Solution one: Time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        preorderInternal(root,res);
        return res;
    }

    private void preorderInternal(Node root,List<Integer> res){
        if(root == null) {return;
        }
        res.add(root.val);
        for(int i = 0; i < root.children.size(); ++i){ preorderInternal(root.children.get(i),res); }}Copy the code

Sequence Traversal of n-tree (429)

Topic describes

Given an n-tree, returns a backward traversal of its node values.

The n-fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

Example 1:

Input: root = [1, null, 3 4-trichlorobenzene, null, 5, 6] output: [[1], [3, 4-trichlorobenzene], [5, 6]]Copy the code

Example 2:

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: [[1], [2, 5-tetrafluorobenzoic],,7,8,9,10 [6], [11], [14]]Copy the code

prompt

  • The height of the tree cannot exceed1000
  • The total number of nodes in the tree is[0, 10 ^ 4)between

Thought analysis

N order traversal of a fork tree, we can also use a binary tree similar to the order traversal, through a queue, each time the size of the queue is recorded, and then traversal these times. So every time we do a while loop, we’re just going to iterate over the number of nodes at one level, and then we’re going to add all the children of that node in turn.

We can also use the addAll method to addAll the children at once.

The code shown

Solution one: Time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {return result;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()){int size = queue.size();
            List<Integer> innerList = new ArrayList<>();
            for(int i = 0; i < size; i++){ Node node = queue.poll(); innerList.add(node.val); queue.addAll(node.children); } result.add(innerList); }return result;
    }
Copy the code

conclusion

In general, the idea of sequential traversal of binary tree /N tree is relatively similar, which is to traverse the number of layers each time by using queues, and then add all the children of nodes of this layer to the queue until the end.

Binary tree /N tree foreorder, middle order (N tree no), subsequent traversal we must firmly grasp, at the same time we should also master the sequence traversal, these basic knowledge must be firmly mastered.