Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Leetcode102 – Sequence traversal of binary trees

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

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). Binary tree: [3,9,20,null,null,15,7],

3
Copy the code

/ 9 20/15 7 Return the sequence traversal result:

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

Analysis of the problem

Method 1

If we want to solve the problem of binary tree sequence traversal, we should first understand what is sequence traversal. Sequential traversal refers to the operation of binary tree traversal step by step according to the level. The main idea is to use hierarchical properties for recursion. Each layer is traversed and the layers are increased at the same time. So as the data recurses, we can get the corresponding level of binary tree array. After the non-null judgment, the node’s value is stored in the corresponding array location. After traversal, we can get all the results of sequential traversal of nodes of binary tree, and traversal mainly adopts the way of sequential traversal. The code is as follows:

public int cnt = 0; public List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { int level = cnt; if(root ! = null){ if(list.size() < level + 1 || list.get(level) == null){ list.add(new ArrayList<>()); list.get(level).add(root.val); } cnt++; levelOrder(root.left,cnt); levelOrder(root.right,cnt); } return list; } public List<List<Integer>> levelOrder(TreeNode root,int value) { int level = value; if(root ! = null){ if(list.size() < level + 1 || list.get(level) == null){ list.add(new ArrayList<>()); } list.get(level).add(root.val); value++; levelOrder(root.left,value); levelOrder(root.right,value); } return list; }Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (n)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.