Java实现二叉树的前中后层序遍历(非递归版）

1. 前序遍历

力扣第144题链接：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

//二叉树的前序遍历为根左右 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) return list; stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); list.add(root.val); //根据栈的先进后出的特点，我们先把右节点压入栈中 if (root.right != null) stack.push(root.right); if (root.left != null) stack.push(root.left); } return list; }

2. 中序遍历

力扣第94题链接：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

//二叉树的中序遍历为左根右 public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) return list; while (!stack.isEmpty()||root!=null) { //当前节点有左孩子的时候，把左孩子压入栈中，然后节点指向左孩子，继续上面的操作，直到左子树上不再有左孩子。 while(root!=null){ stack.push(root); root = root.left; } //弹出当前栈中栈顶的节点作为输出.（弹出的第一个节点是整棵树中最左的那个节点） root = stack.pop(); list.add(root.val); root = root.right; } return list; }

3. 后序遍历

力扣第145题链接：

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

//二叉树的后序遍历为左右根，刚好是“根右左”的逆序， //我们可以修改一下前序遍历的顺序,再对其逆序得到结果 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) return list; stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); list.add(0,root.val);//把新加入的数放在最前面，达到逆序的效果。 //这里与前序遍历相反，我们先压入左节点，再压入右节点 if (root.left != null) stack.push(root.left); if (root.right != null) stack.push(root.right); } return list; }

4. 层序遍历

力扣第102题链接：

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

//二叉树我们借助队列实现 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> q = new LinkedList<>(); if (root == null) return res; q.offer(root); while (!q.isEmpty()) { int n = q.size(); List<Integer>list = new LinkedList<>(); while(n!=0){ n--; list.add(root.val); if(root.left!=null) q.offer(root.left); if(root.right!=null) q.offer(root.right); res.add(list); } } return res; }

力扣的103题要求按之字形层序输出（奇数层从左到右输出，偶数层从右到左输出）只需要在上面的解法中加一个变量level表示当前的层数，当level%2==0时，我们逆序将元素添加进数组，也就是list.add(0,root.val)