1 **
2 * Binary tree first-order traversal non-recursive
3 * @param root
4 */
5 public void preOrder_no_recursive(TreeNode root){
6 if(root == null) return;
7
8 Stackstack = new Stack<>();
9 stack.add(root);
10 while(!stack.isEmpty()){
11 TreeNode tn = stack.pop();
12 System.out.println(tn.val); // Output
13 if(tn.right != null) stack.add(tn.right);
14 if(tn.left != null)stack.add(tn.left);
15 }
16 }
17
18 /**
19 * Binary tree middle-order traversal non-recursive
20 * @param root
21 */
22 public void inOrder_no_recursive(TreeNode root){
23 if(root==null)return;
24 Stackstk = new Stack< TreeNode>();
25 TreeNode p = root;//Auxiliary node
26 stk.add(p);
27 while(stk.isEmpty() == false) {
28 //As long as you have a left child, push the left child onto the stack
29 if(p!=null && p.left!=null) {
30 stk.add(p.left);
31 p = p.left;
32 }else {
33 p = stk.pop();//pop the left child of the top node of the stack --->root node
34 System.out.print(p.val+" ");//Visit
35 if(p!=null && p.right!=null) {//If the stack point element has a right child, a node will be pushed onto the stack
36 stk.add(p.right);
37 p = p.right;
38 }else
39 p = null;//p=stk.pop; has already visited p, and p is set to null
40 }
41 }
42 }
43
44 /**
45 * Binary tree post-order traversal is non-recursive
46 * @param root
47 */
48 public void postOrder_no_recursive(TreeNode root){
49 if(root == null)return;
50 TreeNode p = root;
51 TreeNode pVisit = null;
52 Stackstk = new Stack< TreeNode>();
53 stk.add(p);
54
55 while(stk.isEmpty() == false) {
56 //As long as you have a left child, push the left child onto the stack
57 if(p!=null && p.left!=null) {
58 stk.add(p.left);
59 p = p.left;
60 }else {
61 p = stk.peek();//The top element of the stack is popped first, and there may be a right child
62 if(p.right==null || p.right==pVisit) {//If there is no right child or the right child has already visited, pop out of the stack
63 System.out.print(p.val+" ");
64 pVisit = p;//This is very important. Consider a tree with only right children. It has to be backtracked constantly
65 p = null;//No new node is added, continue popping operation
66 stk.pop();
67 }else {//If there is a right child, the right child is stacked
68 pVisit = p.right;
69 stk.add(p.right);
70 p = p.right;
71 }
72 }
73 }
74 }
1 **
2 * Binary tree first-order traversal non-recursive
3 * @param root
4 */
5 public void preOrder_no_recursive(TreeNode root){
6 if(root == null) return;
7
8 Stackstack = new Stack<>();
9 stack.add(root);
10 while(!stack.isEmpty()){
11 TreeNode tn = stack.pop();
12 System.out.println(tn.val); // Output
13 if(tn.right != null) stack.add(tn.right);
14 if(tn.left != null)stack.add(tn.left);
15 }
16 }
17
18 /**
19 * Binary tree middle-order traversal non-recursive
20 * @param root
21 */
22 public void inOrder_no_recursive(TreeNode root){
23 if(root==null)return;
24 Stackstk = new Stack< TreeNode>();
25 TreeNode p = root;//Auxiliary node
26 stk.add(p);
27 while(stk.isEmpty() == false) {
28 //As long as you have a left child, push the left child onto the stack
29 if(p!=null && p.left!=null) {
30 stk.add(p.left);
31 p = p.left;
32 }else {
33 p = stk.pop();//pop the left child of the top node of the stack --->root node
34 System.out.print(p.val+" ");//Visit
35 if(p!=null && p.right!=null) {//If the stack point element has a right child, a node will be pushed onto the stack
36 stk.add(p.right);
37 p = p.right;
38 }else
39 p = null;//p=stk.pop; has already visited p, and p is set to null
40 }
41 }
42 }
43
44 /**
45 * Binary tree post-order traversal is non-recursive
46 * @param root
47 */
48 public void postOrder_no_recursive(TreeNode root){
49 if(root == null)return;
50 TreeNode p = root;
51 TreeNode pVisit = null;
52 Stackstk = new Stack< TreeNode>();
53 stk.add(p);
54
55 while(stk.isEmpty() == false) {
56 //As long as you have a left child, push the left child onto the stack
57 if(p!=null && p.left!=null) {
58 stk.add(p.left);
59 p = p.left;
60 }else {
61 p = stk.peek();//The top element of the stack is popped first, and there may be a right child
62 if(p.right==null || p.right==pVisit) {//If there is no right child or the right child has already visited, pop out of the stack
63 System.out.print(p.val+" ");
64 pVisit = p;//This is very important. Consider a tree with only right children. It has to be backtracked constantly
65 p = null;//No new node is added, continue popping operation
66 stk.pop();
67 }else {//If there is a right child, the right child is stacked
68 pVisit = p.right;
69 stk.add(p.right);
70 p = p.right;
71 }
72 }
73 }
74 }