典型回答

树的遍历方式多种多样，除了有前，中，后序三种遍历方式，还有层次遍历等。同时每种方式一般可以通过递归的方式实现。但是在面试的过程中，面试官往往会让应聘者通过栈或者队列实现。

前序遍历

前序遍历是指：先遍历根节点，再遍历左节点，最后遍历右节点

List<Integer> output = new ArrayList<>(100);
private void preOrder(TreeNode node) {
   if(node == null) return;
   output.add(node.val);
   preOrder(node.left);
   preOrder(node.right);
}

前序遍历可以通过栈来完成，我们可以先让根节点的右节点入栈和左节点入栈。然后再让其出栈，这样我们就会先获取到左节点，再获取到右节点了。依次循环即可

public List<Integer> preorderWithStack(TreeNode root) {
    List<Integer> output = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if(root == null) return output;
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        output.add(node.val);
        // 先放右再放左
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }
    return output;
}

中序遍历

中序遍历是指：先遍历左节点，再遍历根节点，最后遍历右节点

List<Integer> ints = new ArrayList<>();
private void inOrder(TreeNode node) {
    if(node == null) return;
    inOrder(node.left);
    ints.add(node.val);
    inOrder(node.right);
}

中序遍历时，一定要先遍历到最左边的节点，所以中序遍历不同于前序遍历那种直接根节点入栈出栈即可。

中序遍历的时候，一定要先依次把左节点放入栈中，然后出栈。进行左，中，右的遍历。遇到右节点的时候，依然需要把右节点作为根节点，重新循环上述步骤

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while(node != null || !stack.isEmpty()) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        TreeNode temp = stack.pop();
        list.add(temp.val);
        // 后续遍历该右节点
        node = temp.right;
    }
    return list;
}

后序遍历

后序遍历是指：先遍历左节点，再遍历右节点，最后遍历根节点

List<Integer> ints = new ArrayList<>();
private void postOrder(TreeNode node) {
    if(node == null) return;
    postOrder(node.left);
	postOrder(node.right);
    ints.add(node.val);
}

不同于前序遍历和中序遍历，后续遍历需要两个栈才可以完成，这是因为根节点需要放置到最后面的原因。我们需要一个栈记录遍历的顺序，同时需要另一个栈来记录遍历的结果，如下所示：

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ints = new ArrayList<>();
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    if(root == null) return ints;
    stack1.push(root);
    while(!stack1.isEmpty()) {
       TreeNode node = stack1.pop();
       stack2.push(node);
       if(node.left != null) stack1.push(node.left);
       if(node.right != null) stack1.push(node.right);
    } 
    while(!stack2.isEmpty()) ints.add(stack2.pop().val);
    return ints;
}

层次遍历

层次遍历是指按照树的每一层进行遍历，譬如先遍历根节点，再遍历第一层，第二层，直到每一层都遍历完成。这个时候我们就需要用到先进先出的特性，这个只能用队列实现，如下代码所示：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root != null) queue.offer(root);
    while(!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> ints = new ArrayList<>();
        for(int i = 0; i < n; i ++) {
            TreeNode node = queue.poll();
            ints.add(node.val);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        list.add(ints);
    }
    return list;
}

知识扩展

什么是深度优先和广度优先？

深度优先也叫dfs，是指遍历的时候一直按照某个方向遍历，直到该方向遍历完全后，回退到上个节点，再沿着另外的方向遍历，直到所有节点遍历完全。树的前，中，后序遍历就属于dfs。从上面的算法我们可以看出，dfs的遍历在于递归，一般通过栈完成。
广度优先也叫bfs，是指遍历的时候，直到把根节点周边的节点遍历完后。再把周边节点的每一层遍历，以此类推，直到遍历完成。树的层次遍历就属于bfs。从层次遍历中可以发现，我们一般通过队列完成。

注意，dfs和bfs不止会限于树，图的遍历也可以通过bfs或者dfs完成。

✅二叉树的遍历有几种方式？