【树】——非递归实现二叉树的前序遍历,后序遍历,中序遍历

这是我参与8月更文挑战的第12天，活动详情查看：8月更文挑战

1. 非递归实现二叉树的前序遍历

思路

原来用递归的方式是系统来帮我们压栈，现在我们自己创建一个栈来实现

1.将栈中节点弹出,加入resList集合(需要返回的那个集合）。

2.把被弹出的节点的右子节点和左子节点压入栈中。

3.直到栈为空,遍历结束。

注意
因为是前序遍历所以顺序应该为 root left right
root 弹出时已经加入resList，因为栈是先进后出，所以右子节点先压栈，左子节点再压栈。

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.先把栈中元素弹出
			if (cur == null)
				continue;
			resList.add(cur.val);
			// 先把右边的节点压栈,因为栈是先进后出,前序遍历左子节点先遍历
			stack.push(cur.right);
			stack.push(cur.left);
		}
		return resList;
	}
}

复制代码

2. 非递归实现二叉树的后序遍历

思路

前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
就是左子树先压栈，右子树再压栈,然后再把得到的结果reverse()。其他和前序遍历一样。

代码实现

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);
		return resList;
	}
}
复制代码

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

思路

非递归实现二叉树中序遍历比前两个要难一些。

主要注意最外层的while循环的判断
root != null || !stack.isEmpty()
是为了防止这种情况

栈一直将栈中元素弹出，当把cur弹出的时候栈中是没有元素的，但是树还没有遍历完，root指向的是cur的右子节点 此时 root!=null 但是 stack为空。

而但栈中元素弹出的过程中 ,可能弹出元素的右子节点为空,那么此时
root==null而stack不为空。

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

复制代码

代码实现

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> resList = new ArrayList<>();
		if (root == null)
			return resList;
		Stack<TreeNode> stack = new Stack<>();
		//这个循环条件root==null是指所走的路径没有左子节点了
		while (root != null || !stack.isEmpty()) {
		//然后将右子节点压栈之后又会对右子节点以及其所在的子树执行相同的操作
			while (root != null) { //这个循环是为了一直将左子节点压栈，直到root.left=null,root=root.left=null 退出这个循环
				stack.push(root);
				root = root.left;
			}
			TreeNode cur = stack.pop();
			resList.add(cur.val);
//每弹出一个节点都要将右子节点变为cur，因为此时左子树和当前节点已经遍历完了
			root = cur.right;  
		}
		return resList;
	}
}


复制代码