二叉树的非递归遍历|前中后序遍历

二叉树的非递归遍历

前序遍历-栈

首先我们应该创建一个Stack 用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack。之后我们应该先打印左子树，然后右子树，所以先加入Stack的就是右子树，然后左子树。

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();//1.根节点入栈stack.push(root);//2.栈不为空while (!stack.isEmpty()) {//2.1出栈，需暂时保存出栈元素TreeNode tmp = stack.pop();res.add(tmp.val);//2.2左右子树不为空的情况下，出栈元素的右子树入栈，左子树入栈if (tmp.right != null) {stack.push(tmp.right);}if (tmp.left != null) {stack.push(tmp.left);}}return res;
}

层序遍历-队列

首先我们应该创建一个Queue用来存放节点，首先我们想要打印根节点的数据，此时Queue里面的内容为空，所以我们优先将头结点加入Queue。之后我们应该先打印左子树，然后右子树，所以先加入Queue的就是左子树，然后右子树。

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();//1.根节点入队列queue.offer(root);//2.队列不为空while (!queue.isEmpty()) {//2.1获取当前队列的元素List<Integer> level = new ArrayList<>();int size = queue.size();for (int i = 0; i < size; i++) {//2.1.1出队列，需暂时保存出队元素TreeNode tmp = queue.poll();level.add(tmp.val);//2.1.2左右子树不为空的情况下，出队元素的左子树入队，右子树入队if (tmp.left != null) {queue.offer(tmp.left);}if (tmp.right != null) {queue.offer(tmp.right);}}//2.2当前队列元素加入到res中res.add(level);}return res;
}

中序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树(也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层，同时在返回上层的时候已经处理完毕左子树了。

当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完 左子树->中间(就是一个节点)->右子树）

如果有右节点，其也要进行中序遍历。

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (true) {//1.cur从根节点出发，一直向左保存左子树，直到cur=nullwhile (cur != null) {stack.push(cur);cur = cur.left;}//2.若栈为空，退出循环if (stack.isEmpty()) {break;}//3.出栈TreeNode tmp = stack.pop();res.add(tmp.val);//4.cur指向出栈元素的右子树，//若为空则继续出栈，若不为空再继续向左保存子树cur = tmp.right;}return res;
}

后序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素。

该元素无右子树，或者右子树已经访问过，则可以处理该元素，并用prev记录当前已处理的元素

否则访问右子树，进行后序遍历

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (true) {//1.cur从根节点出发一直向左保存左子树，直到cur=nullwhile (cur != null) {stack.push(cur);cur = cur.left;}//2.若栈为空，退出循环if (stack.isEmpty()) {break;}//3.得到栈顶元素，先不访问（满足条件才可以访问）TreeNode tmp = stack.peek();//4.若栈顶元素无右子树或者右子树已被访问，则可以访问//若prev==tmp.right，则tmp一定是其右子树的根节点。因为此时右子树已访问完毕if (tmp.right == null || tmp.right == prev) {stack.pop();res.add(tmp.val);prev = tmp;} else { //5.cur指向栈顶元素的右子树cur = tmp.right;}}return res;}