树的前中后层序遍历（递归与非递归方式）

Description

LeetCode的第590题与429、589题型类似，都为树（不一定是二叉树）的各种形式的遍历，因此放在一起总结。

对于上图，要求求出前序遍历、后序遍历和层级遍历的结果。

Example

前序遍历结果：[1,3,5,6,2,4]
后序遍历结果：[5,6,3,2,4,1]
层级遍历结果：
[
     [1],
     [3,2,4],
     [5,6]
]

Analysis

对于树我们一般有两种策略：

广度优先搜索（BFS）：从上到下一层一层的遍历树，也就是题目要求的层级遍历。
深度优先搜索（DFS）：从一个根节点开始，一直到达某个叶子节点，然后回到根节点到达另一个分支的叶子节点。根据根节点、左节点和右节点之间的相对顺序，DFS策略可以进一步区分为前序、中序和后序。

根据深度优先搜索与广度优先搜索可以整理出下图的四种情况：

Solution

对于第一题求前序遍历，我们可以使用递归或者循环来完成，实际上这三道题都是如此。我们先看看递归版本：

public class Solution {
	List<Integer> list;
	
    public List<Integer> preorder(Node root) {
    	list = new ArrayList<>();
        if(root == null) return list;
        preorderCore(root);
        return list;
    }

    
    private void preorderCore(Node root) {
    	if(root == null)
    		return;
    	list.add(root.val);
    	for(Node node : root.children)
    		preorderCore(node);
    }
}

前序遍历就是先将根节点放入结果列表中，然后再将左右子节点放入。递归的解法较为简单，下面看看循环的解法：

public class Solution2 {
    public List<Integer> preorder(Node root) {
    	LinkedList<Integer> res = new LinkedList<>();
    	if(root == null)
    		return res;
    	Stack<Node> stack = new Stack<>();
    	stack.push(root);
    	while(!stack.isEmpty()) {
    		Node node = stack.pop();
    		res.add(node.val);
    		Collections.reverse(node.children);
    		for(Node children : node.children) {
    			stack.push(children);
    		}
    	}
    	return res;
    }
}

在递归中我们使用栈来保存接下来要访问的节点。首先我们将根节点压入栈，栈中元素为[1]，然后我们将它弹出至结果列表并把它的子节点翻转并放入栈，此时栈中元素为[4, 2, 3]；由于栈顶元素为3，因此将3弹出至结果列表并把它的子节点翻转并放入栈，此时栈中元素为[4, 2, 6, 5]；栈顶元素为5，因此将5弹出至结果列表，5没有子节点，再把6弹出至结果列表。如此反复，我们便可以通过这种方式得到前序遍历的结果列表[1, 3, 5, 6, 2, 4]。

求后序遍历与这题异曲同工，同样先看看递归版本：

public class Solution {
	List<Integer> list;
	
    public List<Integer> postorder(Node root) {
    	list = new ArrayList<>();
        if(root == null) return list;
        postorderCore(root);
        return list;
    }
    
    private void postorderCore(Node root) {
    	if(root == null)
    		return;
    	for(Node node : root.children)
    		postorderCore(node);
    	list.add(root.val);
    }
}

我们仅仅将list.add(root.val); 这行代码放到了遍历子节点的for语句之后，意味着先将所有子节点加入结果列表，最后再将根节点加入结果列表。下面是使用循环的解法：

public class Solution2 {
    public List<Integer> postorder(Node root) {
    	LinkedList<Integer> res = new LinkedList<>();
    	if(root == null) 
    		return res;
    	
    	Stack<Node> stack = new Stack<>();
    	stack.push(root);
    	while(!stack.isEmpty()) {
    		Node node = stack.pop();
    		res.addFirst(node.val);
    		for(Node children : node.children) {
    			stack.push(children);
    		}
    	}
    	return res;
    }
}

与前序遍历不同的是我们不需要翻转子节点列表，但是每次将结果添加到结果列表头而不是尾。

第三题是层序遍历（广度优先搜索），不像上面两题用递归实现更加简单，我们通过循环来实现会更加简洁明了，思路是使用一个队列而非栈来保存每一层节点：

public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
    	List<List<Integer>> res = new ArrayList<>();
    	if(root == null) return res;
    	Queue<Node> queue = new LinkedList<>();
    	queue.add(root);
    	while(!queue.isEmpty()) {
    		int size = queue.size();
    		List<Integer> list = new ArrayList<>();
    		while(size-- != 0) {
    			Node node = queue.poll();
    			for(Node children : node.children) queue.add(children);
    			list.add(node.val);
    		}
    		res.add(list);
    	}
    	return res;
    }
}