java non recursive implementation of the first middle and second order traversal of binary tree

Traversal of 2-tree in front, middle and back order

Core idea: Stack is used to store nodes. One side traverses, one side puts the node into the stack, takes the node out of the stack and traverses the left subtree or the right subtree of the node when necessary, repeats the above process, and when the stack is empty, the traversal is completed.

Preorder traversal

// Non-recursive 
// Root   Left   Right 
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // Using arrays to store preamble traversal results 
        List<Integer> list = new ArrayList<>();
        if(root==null)  return list;
        
        // Create 1 Stack 
        Stack<TreeNode> st = new Stack<>();
        //cur Point to the root node 
        TreeNode cur = root;
        
        while(!st.isEmpty()||cur!=null){
        
            //1 Edge traverses to the left, 1 The edge puts the traversed node on the stack and the node value into the array 
            while(cur!=null){
                list.add(cur.val);
                st.push(cur);	// Root 
                cur=cur.left;	// Left 
            }
            
            // The pointer points to the top node of the stack (that is, on 1 Nodes), and the top node of the stack is removed from the stack 
            cur = st.pop();
            // The pointer points to the right subtree of the node and starts the following 1 Traversal of wheels 
            cur = cur.right;	// Right 
        }
        return list;
    }
}

Middle order traversal

// Non-recursive 
// Left   Root   Right 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        
      List<Integer> list = new ArrayList<>();
      if(root==null)    return list;
        
      Stack<TreeNode> st = new Stack<>();
       TreeNode cur = root;
      while(!st.isEmpty()||cur!=null){
      //1 Edge traverses to the left, 1 Edge puts the traversed node on the stack 
          while(cur!=null){
              st.push(cur);
              cur = cur.left;	// Left 
          }
          cur = st.pop();
          // Store traversal results 
          list.add(cur.val);	// Root 
          cur = cur.right;		// Right 
      }
      return list;
    }
}

The codes of preorder traversal and middle order traversal are basically the same, but the codes of postorder traversal are not quite the same as them

Post-order traversal

// Non-recursive 
// Left   Right   Root 
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     if(root==null) return list;
     TreeNode cur = root;
     
     // The key is to define 1 A cur Precursor node of 
     TreeNode pre = null;
     Stack<TreeNode> st = new Stack<>();
     while(cur!=null||!st.isEmpty()){
     
     	//1 Edge traverses to the left, 1 Edge puts the traversed node on the stack 
         while(cur!=null){
             st.push(cur);
            cur = cur.left;
         }
         cur = st.pop();
         // If the right node of the node is empty, or the right node has been traversed, the array can store the value of the node (that is, the root we last traversed) 
         if(cur.right==null||cur.right==pre){
             list.add(cur.val);
             pre = cur;
             cur=null;
         }else{// If it is not satisfied, it means that the right node of the node has not been traversed, and then traverses to the right child node 
             st.push(cur);
             cur=cur.right;
         }
     }
     return list;
    }
}