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

Why DFS

I believe that the friends who have learned data structure know that DFS (depth-first search) is a very important search algorithm, may directly say that you feel not conditional you can go to see some algorithm competition. Every one of these games is going to involve DFS in some way or another, and DFS is probably something we all know about but we all know about it in order to avoid being too arrogant to write about it. In order to avoid this embarrassment we are going to take advantage of this activity for a few days to practice, well we don’t have to talk about fat.

PS: THESE days, I found that some fat friends do not know what DFS is. I’d better say it briefly, otherwise this problem will be difficult to do.

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

For example, if we initiate A depth-first search from point A (the following access order is not unique, the second point could be either B or C or D), we might get an access process like A->B->E (no path! Backtrace to A)->C->F->H->G->D (no path, finally backtrace to A,A also has no adjacent node not visited, the search ends). The characteristic of depth-first search is briefly explained: the result of depth-first search must be a connected component of graph. Depth-first searches can be initiated from multiple points. If you sort each node by “end time” during a depth-first search (by creating a list, then adding that node to the end of the list if all of its neighbors have been accessed, and then reversing the entire list), Then we can get what is called “topological sort “, i.e. topological sort. [1]

The title

Given a non-empty binary tree root, return the average value of each level as an array. Answers within 10-5 of the actual answer are acceptable.

Example 1:

Enter: root = [3.9.20.null.null.15.7] output: [3.00000.14.50000.11.00000[no0The average of the layers is3In the first1The average of the layers is14.5In the first2The average of the layers is11. So return [3.14.5.11].Copy the code

Example 2:

Enter: root = [3.9.20.15.7] output: [3.00000.14.50000.11.00000]
Copy the code

Ideas:

Solution a: DFS

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Integer> counts = new ArrayList<Integer>();// Store the number of nodes
        List<Double> sums = new ArrayList<Double>();// Store the sum of all nodes
        dfs(root, 0, counts, sums);
        List<Double> averages = new ArrayList<Double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.add(sums.get(i) / counts.get(i));
        }
        return averages;
    }

    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()) {
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums); }}Copy the code

Solution 2: Try breadth-first search today

You can also use breadth-first search to calculate the level average of a binary tree. The search starts from the root node, traverses all nodes of the same layer in each round, calculates the number of nodes of this layer and the sum of the node values of this layer, and then calculates the average value of this layer.

How do you ensure that each round traverses all nodes of the same layer? We can take a page out of hierarchical traversal, where breadth-first search uses queues to store nodes to be accessed, as long as we ensure that the nodes in the queue are all nodes of the same tier in each round of traversal. Specific practices are as follows:

Initially, the root node is enqueued.

In each round of traversal, all the nodes in the queue are taken out, the number of these nodes and the sum of their node values are calculated, and the average value of these nodes is calculated. Then, all non-empty child nodes of these nodes are added to the queue, and the above operation is repeated until the queue is empty and the traversal is finished.

Since there is only the root node in the queue at the beginning, all nodes in the queue are all nodes of the same layer. In each round of traversal, all nodes of the current layer in the queue are taken out and all nodes of the next layer are added to the queue. Therefore, it can be ensured that all nodes of the same layer are traversed in each round.

In terms of concrete implementation, the number of nodes \textit{size}size in the queue can be obtained before each round of traversal. The traversal only traverses \textit{size}size nodes, which can satisfy all nodes in the same layer in each round of traversal.

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<Double>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(! queue.isEmpty()) {double sum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                TreeNode left = node.left, right = node.right;
                if(left ! =null) {
                    queue.offer(left);
                }
                if(right ! =null) {
                    queue.offer(right);
                }
            }
            averages.add(sum / size);
        }
        returnaverages; }}Copy the code