在研究二叉树的遍历之前，我们需要先看看二叉树的表示方式。
一般来说，我们使用自定义的数据结构或是数组来表示二叉树。
二叉树的数据结构：
public class TreeNode { public int val; // 左孩子 public TreeNode left; // 右孩子 public TreeNode right; }
数组形式表现二叉树
当我们使用数组形式表现二叉树时，我们将数组第一个节点的索引置为「1」，也就是根节点，如果我们通用性的将其当为「x」，那么它的左孩子节点的索引就是「2*x」，右孩子节点的索引为「2*x+1」。
例如下面的二叉树，我们可以使用数组[null, 1, 2, 3, null, 4, 5]来表示（因为根节点的索引需要为1，因此数组第一个元素我们将其置为null）
二叉树中一般有四种遍历方式：前序遍历、中序遍历、后序遍历和层序遍历。它们都可以通过「递归」或是「非递归」实现，递归便于理解但是效率低下且不安全，可能会出现栈溢出；非递归，即采用循环，通常采用栈来完成，会复杂一些，但能够提高效率，降低遍历的消耗。其中『层序遍历』本质上是图的「广度优先搜索」，与另外三种有较大差异，故我们这里只讨论前序、中序和后序遍历方式，层序遍历放在之后进行讨论。
在下面的实现中，我们用一个名为「result」的队列来模拟遍历的顺序
前序遍历访问顺序：根 → 左 → 右
递归实现 public class PreorderTraversal { public List<Integer> preorderTraversal(TreeNode root) { //add()和remove()方法在失败的时候会抛出异常(不推荐),应使用add()和poll()代替 List<Integer> result = new LinkedList<>(); // 进行前序遍历 _preorderTraversal(root, result); return result; } private void _preorderTraversal(TreeNode node, List<Integer> result) { if (null != node) { // 先输出根节点的值，然后再顺序处理左孩子和右孩子 result.add(node.val); _preorderTraversal(node.left, result); _preorderTraversal(node.right, result); } } } 非递归实现实现思路
非递归实现时前序遍历时，我们需要借助栈(Stack)这一数据结构来完成，根据前序遍历「根-左-右」的特点，我们用以下思路来解决：
预处理：将根节点 push 到栈中
通过循环遍历树：
检测栈是否为空，空则结束循环；若非空，则 pop 栈顶元素，并输出栈顶元素的值
判断栈顶元素「右孩子」是否为 null，非空则将其 push 到栈中
判断栈顶元素「左孩子」是否为 null，非空则将其 push 到栈中
在上面思路中，因为栈这一数据结构是「先进后出」的，所以我们先压入右孩子，后压入左孩子，这样最终访问时能够先访问左孩子。
参考代码
这里对于前序、中序和后序遍历的非递归实现，都会给出两种代码，第一种代码较为直观，易于理解；第二种代码属于模版类型的代码，形式统一，便于记忆。
这里先给出符合上述思路，便于理解的代码
public class PreorderTraversal { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); // 1. 将根节点push到栈 Stack<TreeNode> tempStack = new Stack<>(); tempStack.push(root); // 2. 通过循环遍历树 while (!tempStack.empty()) { TreeNode node = tempStack.pop(); result.add(node.val) if (null != node.right) { tempStack.push(node.right); } if (null != node.left) { tempStack.push(node.left); } } return result; } }便于记忆的模版代码
这里为什么给出模版代码？
因为二叉树这东西，看着思路理解很快，但是实际写起来容易忘这忘那，所以这里给出模版代码，我们可以多看几遍模版代码先记下如何使用，在熟练之后就可以得心应手的使用二叉树了。
模版代码的思路
预处理
在遍历二叉树的模版中，我们需要引入一个『辅助节点 curr』保存「当前正在访问的节点」，初始化为根节点，保证栈顶元素始终是 curr 的根节点；每次循环时判断条件为当前栈非空或辅助节点 curr 不为空。
使用循环前序遍历二叉树
对于这个模版，我们要牢记其在循环中的两种情况，这是根据辅助节点 curr 是否为null进行判断的
curr 存在时，表示栈顶元素存在左孩子，将 curr 压入栈并输出 curr 的值，最后将 curr 节点的值指向其左孩子节点
如果 curr 为空(即不存在)，表示栈顶的节点不存在左子树，这是我们弹出栈顶的节点，将 curr 指向被弹出栈顶节点的右孩子节点