[leetcode] breadth first search level traversal general disassembly template

#LeetCode A daily topic 【 Special topic of binary tree 】

• It often involves some problems related to the number of levels of binary trees , For example, you need to do some logical processing on the nodes of each layer of the tree 、 Find the number of layers （ Height ） etc. , Something like this , Can use breadth first search hierarchy traversal to achieve , The general template is as follows

  if (root == null) {
        
      return;
  }
  Deque<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
        
      //  All the current queue elements are out of the queue , Use size The guarantee is a hierarchical outgoing queue , That is, all elements of the current length at the same level are out of the queue 
      for (int i = 0, size = queue.size(); i < size; i++) {
        
          TreeNode node = queue.pop();
          // TODO  Logic processing 
          //  Continue to put its left and right nodes in the queue 
          if (node.left != null) queue.add(node.left);
          if (node.right != null) queue.add(node.right);
      }
  }
  

  The main thing is , Queue all nodes of the same layer together

• Can be applied to LeetCode102 Sequence traversal of binary tree 、LeetCode103 Zigzag sequence traversal of binary tree 、LeetCode107 Sequence traversal of binary tree II、LeetCode116 Fill in the next right node pointer for each node 、LeetCode117 Fill in the next right node pointer for each node II、 LeetCode199 Right side view of binary tree 、LeetCode104 The maximum depth of a binary tree 、LeetCode111 Minimum depth of binary tree etc.

• LeetCode102 Sequence traversal of binary tree

  Put the nodes of each layer into one List in

  public List<List<Integer>> levelOrder(TreeNode root) {
        
          List<List<Integer>> ans = new ArrayList<>();
          if (root == null) {
        
              return ans;
          }
          Deque<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          while (!queue.isEmpty()) {
        
              List<Integer> res = new ArrayList<>();
              //  All the current queue elements are out of the queue , Use size The guarantee is a hierarchical outgoing queue , That is, all elements of the current length at the same level are out of the queue 
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  TreeNode node = queue.pop();
                  //  Continue to put its left and right nodes in the queue 
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
                  res.add(node.val);
              }
              ans.add(res);
          }
          return ans;
   }
  

• LeetCode103 Zigzag sequence traversal of binary tree

  Be similar to 102, It's just that each layer is put into a collection , One head and one tail , That is, from left to right and from right to left

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
      List<List<Integer>> ans = new LinkedList<>();
      if (root == null) return ans;
      Deque<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      boolean left = true;
      while (!queue.isEmpty()) {
        
          LinkedList<Integer> res = new LinkedList<>();
          for (int i = 0, size = queue.size(); i < size; i++) {
        
              TreeNode node = queue.poll();
              if (node.left != null) queue.add(node.left);
              if (node.right != null) queue.add(node.right);
              //  Enter the result set to adjust the order 
              if (left) {
        
                  //  Tail insertion 
                  res.add(node.val);
              } else {
        
                  //  Head insertion 
                  res.addFirst(node.val);
              }
          }
          left = !left;
          ans.add(res);
      }
      return ans;
  }
  

• LeetCode107 Sequence traversal of binary tree II

  It's similar to 102, Only when entering the final result set , It's head insertion , That is, the level traversal is from bottom to top

  public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
          List<List<Integer>> ans = new LinkedList<>();
          if (root == null) {
        
              return ans;
          }
          Queue<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          while (!queue.isEmpty()) {
        
  
              List<Integer> res = new LinkedList<>();
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  TreeNode node = queue.poll();
                  res.add(node.val);
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
              ans.add(0, res);
          }
          return ans;
      }
  

• LeetCode116 Fill in the next right node pointer for each node

  It is necessary to set up between nodes of each layer next Relationship , Breadth first search can be considered , Layer traversal establishes relationships between nodes in each layer

  //  breadth-first , Level traversal （ One layer at a time ）
      public Node connect(Node root) {
        
          if (root == null) return null;
          Deque<Node> queue = new LinkedList<>();
          queue.add(root);
          while (!queue.isEmpty()) {
        
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  Node node = queue.poll();
                  //  Use peek Retrieve what the queue header value is , establish next Relationship 
                  if (i < size - 1) {
        
                      node.next = queue.peek();
                  }
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
          }
          return root;
      }
  

• LeetCode117 Fill in the next right node pointer for each node II

  Consider this question from the perspective of breadth first 106 It doesn't make any difference , Here we only explain the breadth first level traversal

  //  breadth-first , Level traversal （ One layer at a time ）
      public Node connect(Node root) {
        
          if (root == null) return null;
          Deque<Node> queue = new LinkedList<>();
          queue.add(root);
          while (!queue.isEmpty()) {
        
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  Node node = queue.poll();
                  //  Use peek Retrieve what the queue header value is , establish next Relationship 
                  if (i < size - 1) {
        
                      node.next = queue.peek();
                  }
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
          }
          return root;
      }
  

• LeetCode199 Right side view of binary tree

  Simply analyze the meaning of the topic , That is, splice the rightmost node of each layer of the binary tree , The obvious idea of traversing the hierarchy

  public List<Integer> rightSideView(TreeNode root) {
        
          List<Integer> ans = new ArrayList<>();
          if (root == null) return ans;
          Deque<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          while (!queue.isEmpty()) {
        
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  TreeNode node = queue.poll();
                  //  Take the rightmost node 
                  if (i == size - 1) {
        
                      ans.add(node.val);
                  }
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
          }
          return ans;
      }
  

• LeetCode104 The maximum depth of a binary tree

  Find the maximum depth , That is, the maximum number of layers

  public int maxDepthBFS(TreeNode root) {
        
          if (root == null) {
        
              return 0;
          }
          Deque<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          int level = 0;
          while (!queue.isEmpty()) {
        
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  TreeNode node = queue.poll();
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
              //  All the nodes of the first layer are out of the queue , The layer number +1
              level++;
          }
          return level;
      }
  

• LeetCode111 Minimum depth of binary tree

  Find the minimum depth , That is, the layer where the leaf node first appears is the minimum depth

  public int minDepthBfs(TreeNode root) {
        
          if (root == null) return 0;
          Queue<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          int ans = 1;
          while (!queue.isEmpty()) {
        
              for (int i = 0, size = queue.size(); i < size; i++) {
        
                  TreeNode node = queue.poll();
                  //  There is no child node , Leaf node , Minimum number of layers （ depth ） eureka 
                  if (node.left == null && node.right == null) {
        
                      return ans;
                  }
                  if (node.left != null) queue.add(node.left);
                  if (node.right != null) queue.add(node.right);
              }
              ans++;
          }
          return ans;
      }
  

• notes

  There may be more than one solution to the above problem , Breadth first search hierarchy traversal is just one of them 、 It is also the easiest way to think of , But it doesn't mean it's the optimal solution

• summary

  Deal with problems related to the number of layers 、 Or deal with the problems of nodes in each layer , Consider using this method to solve the problem of hierarchical traversal