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

1.1 二叉树前中后遍历的递归解法

树的前中后序的遍历这个是很常见的问题，其递归做法相对简单，这里直接贴代码：

// 前序遍历
public static void preorder(TreeNode treeNode) {
if (treeNode == null) return;
System.out.print(treeNode.val + " ");
preorder(treeNode.left);
preorder(treeNode.right);
}

// 中序遍历
public static void inorder(TreeNode treeNode) {
if (treeNode == null) return;
inorder(treeNode.left);
System.out.print(treeNode.val + " ");
inorder(treeNode.right);
}
// 后序遍历
public static void postorder(TreeNode treeNode) {
if (treeNode == null) return;
postorder(treeNode.left);
postorder(treeNode.right);
System.out.print(treeNode.val + " ");
}


从上面的代码中可以看到，树的前中后序遍历代码结构基本相同，差距只要在何时输出根值，前序遍历一遍历到节点时，先输出根植，中序是遍历完左子节点，后序是最后才输出，理解起来很容易。

1.2 二叉树前中后遍历的非递归解法

接下来我们来看看如何用非递归的方式，实现前中后序遍历：

1.2.1 非递归的前序遍历：（LeetCode 144）

前序遍历：34、35、29、25、33、42、40、39
根据树前序遍历的特点，我们很容易将其与栈的特点相结合，这里简单附上代码：

// 前序遍历的非递归解法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> lists = new ArrayList<>();
if (root == null) return lists;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode temp = null;
while (!stack.isEmpty()) {
temp = stack.pop();
lists.add(temp.val);
// 这里注意，要先压入右子节点，再压入左节点
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
return lists;
}


1.2.2 非递归的中序遍历：（LeetCode 94）

中序遍历：25、29、35、33、34、40、42、39
这个实现的思路，是按照中序遍历的过程：先找到最左的子树，然后返回其父节点，然后遍历右子树，这个返回的动作可以让我们联想到使用栈这个数据结构，实现代码：

// 二叉树非递归的中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root, temp = null;
List<Integer> lists = new ArrayList<>();

// 判断条件：所有栈为空，且节点指向为空，即所有节点已经完成遍历
while (!stack.isEmpty() || node != null) {
// 向左搜索，寻找最左的节点，即中序遍历的第一个节点
while (node != null) {
stack.add(node);
node = node.left;
}
// 对每一个节点进行判断
if (!stack.empty()) {
// 获取当前节点
temp = stack.pop();
// 遍历该节点
lists.add(temp.val);
// 如果该节点为内部节点，则按中序遍历的顺序，遍历其右子节点
node = temp.right;
}
}
return lists;
}


1.2.3 非递归的后序遍历：（LeetCode 145）

非递归的后序遍历比较麻烦，但如果我们发现以下规律，就会变得简单：
例如：

对于后序遍历，结果：25、29、33、35、40、39、42、34
后序遍历的方法，就是先左子树，后右子树，再最后根节点，如果反过来，顺序就变成了：先根节点，后右子树，再左子树，是不是跟先序遍历有点像呢？就是先序遍历根节点遍历之后，下一个是遍历左子树，而下一个再遍历右子树。我们按这种反过来的顺序进行遍历，结果：34、42、39、40、35、33、29、25。很容易发现跟上面后序遍历的结果刚好相反。
因此，后序遍历可以变为：先遍历根节点，后遍历右子树，再遍历左子树，的结果的逆序，我们修改先序遍历的代码，可以得到：

public List<Integer> postorderTraversal_(TreeNode root) {
LinkedList<Integer> lists = new LinkedList<>();
if (root == null) return lists;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode temp = null;
while (!stack.isEmpty()) {
temp = stack.pop();
lists.addFirst(temp.val);
if (temp.left != null) {
stack.push(temp.left);
}
if (temp.right != null) {
stack.push(temp.right);
}
}
return lists;
}


这里使用了LinkedList，目的是为了让我们每一次插入结果，都可以插入到当前结果的最前面，相当于实现逆序的过程。

1.3 层序遍历：（LeetCode 102、103、107）

层序遍历，就是按照每一层的顺序，一层一层的访问，例如：

层序遍历的结果为：[[34], [35, 42], [29, 33, 40, 39], [25]]

// 根据层序遍历的特点，我们很容易想到使用队列，利用广度优先遍历的方式，进行遍历
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> lists = new ArrayList<>();
List<Integer> arrays = new ArrayList<>();
TreeNode temp = null;
while (!queue.isEmpty()) {
int n = queue.size();
// 这里通过读取队列的元素，获取这一层有多少个元素
for (int i = 0; i < n; i++) {
temp = queue.poll();
arrays.add(temp.val);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
// 将每一层的数据放入到链表中
lists.add(new ArrayList<>(arrays));
arrays.clear();
}
return lists;
}

2 树的前中后层序遍历

上面讲的都是二叉树，那对于一棵普通的树，其前中后序遍历，是如何呢：

2.1 前序遍历：（LeetCode 589）

// 递归实现
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
helper(result, root);
return result;
}
private void helper(List<Integer> list, Node root) {
list.add(root.val);
for (Node node: root.children
) {
helper(list, node);
}
}

// 非递归的N叉树前序遍历
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
result.add(temp.val);
// 注意这里要入栈的顺序是从右边最后一个子树开始
for (int i = temp.children.size() - 1; i >= 0; i--) {
stack.add(temp.children.get(i));
}
}
return result;


2.2 中序遍历：

发现 LeetCode 没有N叉树的中序遍历，关于中序遍历，我们要注意：先遍历最左的一个子树，然后根节点，然后才是遍历其他子节点。

遍历结果：5、3、6、1、2、4

2.3 后序遍历：（LeetCode 590）

后序遍历：5、6、3、2、4、1
规律：遍历每个节点，先遍历节点的子节点，最后输入根节点。
这里可以参考二叉树的后序遍历，也使用逆转考虑的方法，先遍历根节点，然后按逆序访问孩子节点，最后将结果进行逆序处理。

// 递归实现：
public List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
helper(result, root);
return result;
}
private void helper(List<Integer> list, Node root) {
for (Node node : root.children
) {
helper(list, node);
}
list.add(root.val);
}
// 非递归：
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;

Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
result.add(temp.val);
stack.addAll(temp.children);
}
// 将结果进行逆序
Collections.reverse(list);
return list;
}


2.4 层序遍历：（LeetCode 429）

// N叉树的层序遍历
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> lists = new ArrayList<>();
if (root == null) {
return lists;
}

Queue<Node> queue = new LinkedList<>();
queue.add(root);
List<Integer> list = new ArrayList<>();
Node temp = null;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
temp = queue.poll();
// 跟二叉树的层序遍历的区别在于，这里加入的是所有子树
queue.addAll(temp.children);
list.add(temp.val);
}
lists.add(new ArrayList<>(list));
list.clear();
}

return lists;
}