This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

Topic describes

Each node of the binary tree is printed from top to bottom, and nodes of the same level are printed from left to right.

For example: given a binary tree: [3,9,20, NULL,null,15,7], 3 / \ 9 20 / \ 15 7 Returns: [3,9,20,15,7] Warning: Total number of nodes <= 1000 https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This topic describes the data structure of trees and queues.
  • I adopted the method of BFS to solve this problem. For those of you who have not used BFS, a brief introduction to the BFS algorithm.
  • The full name of BFS is Breadth First Search, also called Breadth First Search in Chinese. So called width first. Is to try to access nodes of the same layer every time. If the same layer is accessed, access the next layer.
  • The path found by the BFS algorithm is the shortest legal path from the starting point. This is very important, when you see the shortest path problem, you can think about the BFS algorithm in your mind.

Through the code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> nodeValList = new ArrayList<>();
        bfs(root, nodeValList);
        int size = nodeValList.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = nodeValList.get(i);
        }
        return ans;
    }

    public void bfs(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()) {int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                ans.add(node.val);
                if(node.left ! =null) {
                    queue.add(node.left);
                }
                if(node.right ! =null) {
                    queue.add(node.right);
                }
            }
        }
    }
}
Copy the code
  • In the above code, pay attention to the size of the queue when using it. Queue.size () is used to dynamically fetch the size of the queue. In order to ensure that all elements of the current layer are fetched, we need to define the size variable to determine the size of the current layer and fetch all elements of the current layer.

conclusion

  • The BFS solution is O(n) in time and O(n) in space.
  • Stick to the daily question, come on!