102. Sequence traversal of binary trees

Their thinking

DFS and BFS

Let’s first look at the code comparison between DFS traversal and BFS traversal on a binary tree.

DFS traversal uses recursion:

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
 dfs(root.right); } Copy the code

BSF traversal uses queue data structures:

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayQueue<>();
    queue.add(root);
    while(! queue.isEmpty()) {        TreeNode cur = queue.poll();
 if(cur.left ! = null) { queue.add(cur.left);  }  if(cur.right ! = null) { queue.add(cur.right);  }  } } Copy the code

DFS traversal code is much cleaner than BFS because the recursive approach implicitly uses the stack of the system and does not require direct maintenance of a data structure. Although DFS and BFS traverse all nodes of a binary tree, they traverse nodes in different order.

DFS recursively

/ * * * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 * TreeNode right;  * TreeNode(int x) { val = x; } *}* /class Solution {  public List<List<Integer>> levelOrder(TreeNode root) {  List<List<Integer>> list = new ArrayList<>();  if (root == null) return list;  dfs(root,1, list);  return list;  }  private void dfs(TreeNode root, int level, List<List<Integer>> list) { // The current collection is less than the tree depth (level) if(list.size() < level) { // Add an empty collection to the returned result list.add(new ArrayList());  } // Get the empty set by subtracting 1 and add the tree value list.get(level - 1).add(root.val);  // Determine the left and right subtrees, go to the next layer, tree depth increased by 1 if(root.left ! = null) { dfs(root.left, level + 1, list);  }  if(root.right ! = null) { dfs(root.right, level + 1, list);  }  } } Copy the code

BFS iterative mode

/ * * * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 * TreeNode right;  * TreeNode(int x) { val = x; } *}* /class Solution {  public List<List<Integer>> levelOrder(TreeNode root) {  List<List<Integer>> list = new ArrayList<>();  if (root == null) return list;  Deque<TreeNode> deq = new ArrayDeque<>();  deq.add(root);  while(! deq.isEmpty()) { int n = deq.size();  List<Integer> level = new ArrayList<>();  for (int i = 0; i < n; i++) { // The variable I has no real meaning, just to loop n times TreeNode cur = deq.poll();  level.add(cur.val);  if(cur.left ! = null) deq.add(cur.left); if(cur.right ! = null) deq.add(cur.right); }  list.add(level);  }  return list;  }  } Copy the code

Some pictures from the network, copyright to the original author, delete.Copy the code