This is the 12th day of my participation in the August Text Challenge.More challenges in August

1. Non-recursive implementation of binary tree preorder traversal

Train of thought

The original recursive way is the system to help us push the stack, now we create a stack to achieve

1. Pop the node from the stack and add it to the resList collection (the collection that needs to be returned).

2. Push the right and left child nodes of the ejected node to the stack.

3. The traversal is complete until the stack is empty.

Root left and right are added to the resList when root pops up. The right child node is pushed first and the left child node is pushed again.

class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {

		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		List<Integer> resList = new ArrayList<>();
		if (root == null)
			return resList;
		while(! stack.isEmpty()) { TreeNode cur = stack.pop();// 1. Pop the stack element first
			if (cur == null)
				continue;
			resList.add(cur.val);
			// Push the right node first, because the stack is first and then out, the first order traverses the left child node first
			stack.push(cur.right);
			stack.push(cur.left);
		}
		returnresList; }}Copy the code

2. Non-recursive implementation of binary tree after the order traversal

Train of thought

The preceding traversal is root -> left -> right, and the latter is left -> right -> root. You can change the pre-order traversal to root -> right -> left so that the order is reversed from the post-order traversal. That is, the left subtree is pushed, the right subtree is pushed again, and the result is reversed (). The others are the same as the preceding traversal.

Code implementation

class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> resList = new ArrayList<>();
		if (root == null)
			return resList;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while(! stack.isEmpty()) { TreeNode cur = stack.pop();if (cur == null)
				continue;
			resList.add(cur.val);
			stack.push(cur.left);
			stack.push(cur.right);
		}
		Collections.reverse(resList);
		returnresList; }}Copy the code

3. Non-recursive implementation of binary tree middle order traversal

Train of thought

Non-recursive implementation of binary tree traversal is a little more difficult than the first two.

Focus on the outermost while loop root! = null || ! Stack.isempty () is designed to prevent this

The stack keeps popping elements out of the stack, so when you pop cur there are no elements in the stack, but the tree hasn’t been traversed yet, so root is pointing to the right child of cur and root! =null but the stack is empty.

When an element is ejected from the stack, the right child node of the ejected element may be empty, so root==null and stack is not empty.

	TreeNode cur = stack.pop();
			resList.add(cur.val);
			root = cur.right;  

Copy the code

Code implementation

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> resList = new ArrayList<>();
		if (root == null)
			return resList;
		Stack<TreeNode> stack = new Stack<>();
		// The loop condition root==null means that the path has no left children
		while(root ! =null| |! stack.isEmpty()) {// Then push the right child and do the same for the right child and its subtree
			while(root ! =null) { // This loop is used to push the left child node until root.left=null,root=root.left=null exits the loop
				stack.push(root);
				root = root.left;
			}
			TreeNode cur = stack.pop();
			resList.add(cur.val);
// Change the right child to cur every time a node pops up, because the left subtree and the current node are already traversed
			root = cur.right;  
		}
		returnresList; }}Copy the code