二叉树的后序遍历-非递归版

本文约定用“打印”这个术语来表示执行某个操作。

在这里插入图片描述

用两个栈来实现

先头节点入栈，然后弹出节点但是接着不打印，而是再次放到一个收集栈里，然后先压左子树再压右子树，这样原本弹出栈的顺序应该是根右左，但是经过这个收集栈之后就变成了左右根，这样的话就能够实现后序遍历。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public static List<Integer> postorderTraversal(TreeNode head) {
		List<Integer> ans = new ArrayList<>();
		if(head!=null){
			Stack<TreeNode> stack = new Stack<>();
			Stack<TreeNode> collect = new Stack<>();
			stack.push(head);
			while(!stack.isEmpty()){
				head = stack.pop();
				collect.push(head);

				if(head.left!=null){
					stack.push(head.left);
				}

				if(head.right!=null){
					stack.push(head.right);
				}
			}

			while (!collect.isEmpty()){
				ans.add(collect.pop().val);
			}
		}
		return ans;
	}

用一个栈来实现

刚开始，我们用h来表示头节点，如果始终没有打印过节点，则h就一直是头节点。一旦打印过节点，则h就变成上一次打印的节点。如果有左子树并且左子树没有处理过，则左子树进栈。如果有右子树并且右子树没有处理过，则右子树进栈。如果左子树、右子树为空或者都处理过了，则打印并将h指向弹出的节点。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static List<Integer> postorderTraversal(TreeNode h) {
		List<Integer> ans = new ArrayList<>();
		if(h!=null){
			Stack<TreeNode> stack = new Stack<>();
			stack.push(h);
			while(!stack.isEmpty()){
				TreeNode cur = stack.peek();
				if(cur.left!=null&&h!=cur.left&&h!=cur.right){
					stack.push(cur.left);
				}else if(cur.right!=null&&h!=cur.right){
					stack.push(cur.right);
				}else{
					ans.add(cur.val);
					h=stack.pop();
				}
			}
		}
		return ans;
	}