Traversing binary trees in non recursive pre -, middle -, and post order

1 The former sequence traversal

The preorder traversal is ： root 、 Left 、 Right , We can use a Stack To complete the traversal , The general idea is as follows ：

• The first time the root node is stacked , Then every time the top element comes out of the stack , Print the value of the root node value;
• The right node of the root node is stacked ;
• The left node of the root node is stacked ;
  Here is the right node advanced stack , Then the left node goes into the stack , Then the next time it comes out of the stack, the left node comes out first , That is, first traverse the left node of the root node .

Reference code ：

public void preOrder(TreeNode root){
    
	if(root == null)return;
	LinkedList<TreeNode> stack = new LinkedList<>();
	stack.addLast(root);
	while(!stack.isEmpty()){
    
		root = stack.removeLast();
		System.out.print(root.val + " ");
		if(root.right != null)stack.addLast(root.right);// Right child node first stack 
		if(root.left != null)stack.addLast(root.left);// Left child node backward stack 
    }
    
}

---

2 In the sequence traversal

The preorder traversal is ： Left 、 root 、 Right , We can also use a Stack To complete the traversal , The general idea is as follows ：

• Put the root node on the stack , The left child is not empty , The left child enters the stack , The left child of the left child is not empty , Left child's left child enters the stack …, Until I met null;
• encounter null, Stack an element out of the stack , Print value, Determine whether the stack element has a right child , If you have any , The right child enters the stack , Repeat step 1 , About to put its left child into the stack .

Reference code ：

public void inOrder(TreeNode root){
    
   if(root == null)return;
   LinkedList<TreeNode> stack = new LinkedList<>();
   while(!stack.isEmpty() || root != null){
    
     if(root != null){
    
       stack.addLast(root);
       root = root.left;  // Put the left child into the stack every time 
     }
	 else{
    
        root = stack.removeLast();
        System.out.print(root.val + " ");
        root = root.right;// Next cycle , The right child enters the stack 
     }
   }
}

---

3 After the sequence traversal

The post order traversal order is ： Left 、 Right 、 root . We need to use 2 Stack to complete . The general idea is as follows ：

• Put the root node on the stack for the first time 1, Later, every time the top element of the stack comes out of the stack and enters the stack 2;
• The left child of the root node is not empty , The left child enters the stack 1;
• The right child of the root node is not empty , The right child enters the stack 1;
• Repeat the above operation （ At this time, the root node does not need to be stacked ）

In this case , Stack 2 The order of elements from the bottom of the stack to the top of the stack is ： root 、 Right 、 Left . So stack 2 After a stack exit , The stack order is left 、 Right 、 root .

public void postOrder(TreeNode root){
    
  if(root== null)return;
  LinkedList<TreeNode> stack1 = new LinkedList<>();
  LinkedList<TreeNode> stack2 = new LinkedList<>();
  stack1.addLast(root);
  while(!stack1.isEmpty()){
    
	root = stack1.removeLast();
	if(root.left != null)stack1.addLast(root.left);
	if(root.right != null)stack1.addLast(root.right);
	stack2.addLast(root);
  }
  while(!stack2.isEmpty()){
    
    TreeNode node = stack2.removeLast();
    System.out.print(node.val + " ");
  } 
  
}

---

test ：

public static void main(String[] args) {
    
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        root.left = left;
        root.right = right;

        System.out.println(" Preorder traversal results ：");
        preOrder(root);

        System.out.println();
        System.out.println(" Middle order traversal result ：");
        inOrder(root);

        System.out.println();
        System.out.println(" Subsequent traversal results ：");
        postOrder(root)
}

---

( End )