二叉树遍历

二叉树遍历主要为前序、中序、后序，以及层序四种遍历方式；而前三者的实现上又可分为递归实现和非递归实现，两种方式都要熟练运用。

递归版本

二叉树的前中后序遍历是二叉树结构的最基本算法，采用递归的写法可以快速，简洁地实现该功能，但同时，由于递归方法过于简单，面试中往往会考察非递归版本。

我们先来看下二叉树节点的结构：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

我们可以先来看下二叉树各种遍历顺序：

其实很好记，就是中间节点在最前面、中间和最后面输出，而左右的相对顺序是固定的。

我们来看个图，可能会更加直观一些：

先序遍历顺序：

中序遍历顺序：

后序遍历顺序：

递归版本代码实现：

先序遍历：

public void preOrder(TreeNode root) {
    if (root == null)
        return;
    System.out.print(root.val + " "); // 输出控制
    preOrder(root.left);
    preOrder(root.right);
}

而中序遍历和后序遍历则只需修改输出控制的位置：