Topic of “Code Random Records”: Traversal of Binary Tree

0. Summary of traversal methods of binary tree

• There are two main ways to traverse a binary tree
  • Depth-first traversal: Go deep first, and then go back when you encounter a leaf node.
  • Breadth-first traversal: Traverse layer by layer.
• Further expansion from depth-first traversal and breadth-first traversal, the following traversal methods are available
  • Depth-first traversal
    • Preorder traversal (recursive method, iterative method)
    • Inorder traversal (recursive method, iterative method (it is best to use unified iterative method))
    • Post-order traversal (recursive method, iterative method)
  • breadth first traversal
    • Hierarchical traversal (recursive method (rare), iterative method)
• The front, middle and back in the depth-first traversal refer to the traversal order of intermediate nodes
  
• other
  • The recursive method is often used to implement depth-first traversal, that is, to implement pre-middle-post order traversal. It is more convenient to use recursion.
  • Stack is actually an implementation structure of recursion, that is to say, the logic of traversal in front, middle and back order can actually be realized in a non-recursive way with the help of stack.
  • Breadth-first traversal is generally implemented using a queue, which is also determined by the first-in-first-out characteristics of the queue, because a first-in first-out structure is required to traverse the binary tree layer by layer.

1. Recursive traversal of binary tree

• Preorder recursive traversal

  class Solution {<!-- -->
  public:
      void traversal(TreeNode* cur, vector<int> & amp; vec) {<!-- -->
          if (cur == NULL) return;
          vec.push_back(cur->val); // Medium
          traversal(cur->left, vec); // left
          traversal(cur->right, vec); // right
      }
      vector<int> preorderTraversal(TreeNode* root) {<!-- -->
          vector<int> result;
          traversal(root, result);
          return result;
      }
  };
  

  With pre-order traversal, in-order traversal and post-order traversal just change the order of traversal

• Inorder recursive traversal

  void traversal(TreeNode* cur, vector<int> & amp; vec) {<!-- -->
      if (cur == NULL) return;
      traversal(cur->left, vec); // left
      vec.push_back(cur->val); // Medium
      traversal(cur->right, vec); // right
  }
  

• Post-order recursive traversal

  void traversal(TreeNode* cur, vector<int> & amp; vec) {<!-- -->
      if (cur == NULL) return;
      traversal(cur->left, vec); // left
      traversal(cur->right, vec); // right
      vec.push_back(cur->val); // Medium
  }
  

2. Iterative traversal of binary tree

• Preorder iterative traversal
  The pre-order traversal is middle and left, and each time the middle node is processed first, then the root node is put into the stack first, then the right child is added to the stack, and then the left child is added.
  

  class Solution {<!-- -->
  public:
      vector<int> preorderTraversal(TreeNode* root) {<!-- -->
          stack<TreeNode*> st;
          vector<int> result;
          if (root == NULL) return result;
          st. push(root);
          while (!st.empty()) {<!-- -->
              TreeNode* node = st.top(); // middle
              st. pop();
              result.push_back(node->val);
              if (node->right) st.push(node->right); // right (empty nodes are not pushed into the stack)
              if (node->left) st.push(node->left); // left (empty nodes are not pushed into the stack)
          }
          return result;
      }
  };
  

• Post-order iteration traversal
  The preorder traversal is middle left, and the subsequent traversal is left left, then we only need to adjust the code order of the preorder traversal to become middle right left The traversal order of strong>, and then reverse the result array, the output result order is left and right, as shown in the figure below
  

  class Solution {<!-- -->
  public:
      vector<int> postorderTraversal(TreeNode* root) {<!-- -->
          stack<TreeNode*> st;
          vector<int> result;
          if (root == NULL) return result;
          st. push(root);
          while (!st.empty()) {<!-- -->
              TreeNode* node = st. top();
              st. pop();
              result.push_back(node->val);
              if (node->left) st.push(node->left); //Compared to pre-order traversal, this changes the stacking order (empty nodes are not pushed into the stack)
              if (node->right) st.push(node->right); // Empty nodes are not pushed into the stack
          }
          reverse(result.begin(), result.end()); // After reversing the result, it is in the order of left and right
          return result;
      }
  };
  

• Inorder iteration traversal
  Think about it, the in-order iterative traversal cannot use the above routine at all, so if the in-order is considered, it is recommended to use the unified iteration method of the binary tree. It is very convenient to use the unified iteration method of the binary tree.

3. Unified iteration method of binary tree

• Taking in-order traversal as an example, it is mentioned that using a stack cannot solve the inconsistency between accessing nodes (traversing nodes) and processing nodes (putting elements into the result set) at the same time. Then we will put the visited node into the stack, and put the node to be processed into the stack but mark it. Marking method: After the node to be processed is placed on the stack, then a null pointer is placed as a mark. This method is called tagging

• Inorder unified iterative traversal
  

  class Solution {<!-- -->
  public:
      vector<int> inorderTraversal(TreeNode* root) {<!-- -->
          vector<int> result;
          stack<TreeNode*> st;
          if (root != NULL) st. push(root);
          while (!st.empty()) {<!-- -->
              TreeNode* node = st. top();
              if (node != NULL) {<!-- -->
                  st.pop(); // Pop the node to avoid repeated operations, and then add the right, middle and left nodes to the stack
                  if (node->right) st.push(node->right); // Add the right node (empty nodes are not pushed into the stack)
  
                  st.push(node); // add middle node
                  st.push(NULL); // The middle node has been visited, but it has not been processed yet, and an empty node is added as a mark.
  
                  if (node->left) st.push(node->left); // Add the left node (empty nodes are not pushed into the stack)
              } else {<!-- --> // Put the next node into the result set only when an empty node is encountered
                  st.pop(); // pop the empty node
                  node = st.top(); // Retrieve the elements in the stack
                  st. pop();
                  result.push_back(node->val); // Add to the result set
              }
          }
          return result;
      }
  };
  

  With this code, the pre-order code and post-order code just modify the traversal order

• Preorder unified iterative traversal

  class Solution {<!-- -->
  public:
      vector<int> preorderTraversal(TreeNode* root) {<!-- -->
              ...
      ...
                  st. pop();
                  if (node->right) st.push(node->right); // right
                  if (node->left) st.push(node->left); // left
                  
                  st.push(node); // middle
                  st. push(NULL);
      ...
              ...
      }
  };
  

• post-order unified iterative traversal

  class Solution {<!-- -->
  public:
      vector<int> postorderTraversal(TreeNode* root) {<!-- -->
          ...
  ...
                  st. pop();
                  st.push(node); // middle
                  st. push(NULL);
  
                  if (node->right) st.push(node->right); // right
                  if (node->left) st.push(node->left); // left
          ...
  ...
      }
  };
  

4. Layer order traversal

• Layer-order traversal needs to be realized by borrowing an auxiliary data structure, namely queue. The queue is first-in-first-out, which conforms to the logic of layer-by-layer traversal, while using the stack first-in-last-out is suitable for simulating the logic of depth-first traversal, which is recursion. And this layer order traversal method is the breadth-first traversal in graph theory, but we apply it to the binary tree .gif” alt=”Please add a picture description”>
• Iterative method

  class Solution {<!-- -->
  public:
      vector<vector<int>> levelOrder(TreeNode* root) {<!-- -->
          queue<TreeNode*> que;
          if (root != NULL) que. push(root);
          vector<vector<int>> result;
          while (!que.empty()) {<!-- -->
              int size = que. size();
              vector<int> vec;
              // Be sure to use a fixed size here, do not use que.size(), because que.size is constantly changing
              for (int i = 0; i < size; i ++ ) {<!-- -->
                  TreeNode* node = que. front();
                  que. pop();
                  vec.push_back(node->val);
                  if (node->left) que. push(node->left);
                  if (node->right) que. push(node->right);
              }
              result. push_back(vec);
          }
          return result;
      }
  };
  

• Recursive method (this seems to be relatively rare)

  # recursive method
  class Solution {<!-- -->
  public:
      void order(TreeNode* cur, vector<vector<int>> & amp; result, int depth)
      {<!-- -->
          if (cur == nullptr) return;
          if (result. size() == depth) result. push_back(vector<int>());
          result[depth].push_back(cur->val);
          order(cur->left, result, depth + 1);
          order(cur->right, result, depth + 1);
      }
      vector<vector<int>> levelOrder(TreeNode* root) {<!-- -->
          vector<vector<int>> result;
          int depth = 0;
          order(root, result, depth);
          return result;
      }
  };