今天我想来说说一道很常见的面试题目 —— 关于 二叉树 前中 后序遍历 的实现。本文将以递归和非递归方式实现这 3 种遍历方式，代码都比较短，可以放心食用。

先简单说明一下这 3 种遍历方式有什么不同 —— 对于每种遍历，树中每个结点都需要经过 3 次（对于叶结点，其左右子树视为空子树），但 前序遍历 在第一次遇到结点时就立即访问， 中序遍历 是在第二次遇到结点时访问，后序遍历则是第三次访问。

所以前中后序遍历访问结点的顺序分别是中左右、左中右、左右中。「中」表示当前结点，「左右 」表 示当前结点的左右子树。

下面让我们一起来看下代码是怎么实现的吧。

递归版

前序遍历

 public static void preOrderRecur(Node head) {
 if (head == null) {
 return;
 }
 System.out.print(head.value + " ");
 preOrderRecur(head.left);
 preOrderRecur(head. right );
 }
复制代码
 

中序遍历

 public static void inOrderRecur(Node head) {
 if (head == null) {
 return;
 }
 inOrderRecur(head.left);
 System.out.print(head.value + " ");
 inOrderRecur(head.right);
 }
复制代码
 

后序遍历

 public static void posOrderRecur(Node head) {
 if (head == null) {
 return;
 }
 posOrderRecur(head.left);
 posOrderRecur(head.right);
 System.out.print(head.value + " ");
 }
复制代码
 

非递归版

前序遍历

public static void preOrderUnRecur( Node  head) {
 if (head != null) {
 Stack<Node> stack = new Stack<Node>();
 stack.add(head);
 while (!stack.isEmpty()) {
 head = stack.pop();
 System.out.print(head.value + " ");
 if (head.right != null) {
 stack. push (head.right);
 }
 if (head.left != null) {
 stack.push(head.left);
 }
 }
 }
 }
复制代码
 

中序遍历

public static void inOrderUnRecur(Node head) {
 if (head != null) {
 Stack<Node> stack = new Stack<Node>();
 while (!stack.isEmpty() || head != null) {
 if (head != null) {
 stack.push(head);
 head = head.left;
 } else {
 head = stack.pop();
 System.out.print(head.value + " ");
 head = head.right;
 }
 }
 }
 }
复制代码
 

后序遍历

public static void posOrderUnRecur(Node head) {
 if (head != null) {
 Stack<Node> s1 = new Stack<Node>();
 Stack<Node> s2 = new Stack<Node>();
 s1.push(head);
 while (!s1.isEmpty()) {
 head = s1.pop();
 s2.push(head);
 if (head.left != null) {
 s1.push(head.left);
 }
 if (head.right != null) {
 s1.push(head.right);
 }
 }
 while (!s2.isEmpty()) {
 System.out.print(s2.pop().value + " ");
 }
 }
 }
复制代码
 

以上就是二叉树的 3 种遍历方式，你学会了吗？

原创首发于「不只 Java 」，更多 Java 内容，欢迎关注。