非递归实现二叉树的中序遍历

在这里插入图片描述

二叉树的中序遍历

代码实现逻辑:

1)来到某一个子树的头节点，整条左边界进栈，一直到整条左边界遍历完；

2)从栈中弹出节点，打印（这里的打印是指可以做某个动作，比如此处是将节点值添加到结果链表），把弹出打印节点的右子树看作是新的子树的头节点，然后重复步骤1）； 3)当没有子树并且栈为空了，结束

注意如果右子树为空，可以假定它执行了比如步骤1)但是什么都没有干成，这样更好理解一些。

代码实现

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


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