二叉树的 DFS 遍历方式常见的一般有 3 种，分别是前序遍历，中序遍历以及后续遍历。这里的前中后是相对于根节点来说的，先遍历根节点就是前序遍历，后遍历根节点就是后续遍历。无论哪种遍历方式都是左子树比右子树先遍历，他的访问顺序如下图所示，注意根节点的位置。当然这些只是我们常见的遍历方式，解有些题的时候是可以交换的，比如先遍历右子树在遍历左子树，最后在遍历根节点。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
1，二叉树的前序遍历。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> mList = new ArrayList<>();
preHelper(root, mList);
return mList;
}
// 二叉树的前序遍历。
public void preHelper(TreeNode root, List<Integer> mList) {
if (root == null)// 如果节点为空，直接返回。
return;
mList.add(root.val);// 先访问当前节点。
preHelper(root.left, mList);// 递归访问左子树。
preHelper(root.right, mList);// 递归访问右子树。
}
2，二叉树的中序遍历。
public void inorder(TreeNode root, List<Integer> mList) {
if (root == null) //递归的终止条件。
return;
inorder(root.left, mList); //递归遍历左子节点。
mList.add(root.val); //访问当前节点。
inorder(root.right, mList); //递归遍历右子节点。
}
3，二叉树的后序遍历。
public void postorder(TreeNode root, List<Integer> mList) {
if (root == null) //递归的终止条件。
return;
postorder(root.left, mList); //递归遍历左子节点。
postorder(root.right, mList); //递归遍历右子节点。
mList.add(root.val);
}
上面的递归还可以换个方式来写，其实原理都类似，把他合并在一起了。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> mList = new ArrayList<>();
if (root == null)
return mList;
// 先遍历左子树和右子树的结果。
List<Integer> leftRes = preorderTraversal(root.left);
List<Integer> rightRes = preorderTraversal(root.right);
// 合并。
// 如果是前序遍历，合并顺序是：[当前节点]->[左子树的结果]->[右子树的结果]
// 如果是中序遍历，合并顺序是：[左子树的结果]->[当前节点]->[右子树的结果]
// 如果是后序遍历，合并顺序是：[左子树的结果]->[右子树的结果]->[当前节点]
mList.add(root.val);//这一行放的位置决定了是什么样的遍历方式。
mList.addAll(leftRes);
mList.addAll(rightRes);
return mList;
}
上面两种方式使用的都是递归的写法，当然我们还可以使用非递归的写法。二叉树的非递归写法一般是结合栈来实现的，因为栈是先进后出的，而递归实际上就相当于在不停的压栈和出栈。
1，非递归前序遍历。
我们先来看下二叉树的前序遍历使用非递归写法的实现方式，因为前序遍历是先遍历根节点在遍历两个子树，最开始的时候先把根节点入栈，然后出栈的时候先打印这个出栈的节点值，接着在把出栈节点的右子节点和左子节点分别入栈（如果有右子节点或者左子节点），注意这里是左子节点后入栈，因为先打印的是左子节点，后入栈的最先出栈，这里顺序不能搞反了，如下图所示，总结一下就是：
- 1，根节点入栈。
- 2，栈顶节点出栈，打印出栈节点的值。
- 3，如果出栈的节点有右子节点，把他的右子节点添加到栈中。
- 4，如果出栈的节点有左子节点，把他的左子节点添加到栈中。
- 5，重复上面的2,3,4，直到栈为空。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> preList = new ArrayList<>();
if (root == null)
return preList;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);// 先把根节点入栈。
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();// 出栈。
preList.add(cur.val);// 打印出栈的节点。
// 先把右子树压栈在把左子树压栈。
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
return preList;
}
2，非递归中序遍历
因为中序遍历是先打印左子树，在打印根节点，最后在打印右子树，所以当遍历到一个节点的时候我们要沿着的他的左子节点一直往下走，顺便把这些左子节点全部压栈，直到没有左子节点为止。然后栈顶元素出栈，打印出栈元素的值，继续使用上面的方式遍历出栈元素的右子节点……，如下图所示，总结一下就是：
- 1，如果当前节点不为空就沿着他的左子节点一直往下走，顺便把走过的节点全部入栈，直到没有左子节点为止。
- 2，如果当前节点为空，栈顶元素出栈，打印出栈的元素。
- 3，访问出栈的右子节点，重复1,2，直到当前节点和栈为空。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorderList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
// 找当前节点的左子节点，一直找下去，直到为空为止。
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();// 出栈。
inorderList.add(root.val);// 打印出栈的节点。
root = root.right;// 遍历出栈节点的右子树。
}
return inorderList;
}
3，非递归后序遍历
后续遍历的非递归有两种实现方式，我们先来看第一种。二叉树的后续遍历是 [左->右->根]，前序遍历是：[根->左->右]，在前序遍历中如果遍历完根节点之后先遍历右子树在遍历左子树就变成了：[根->右->左]，正好和后续遍历相反，最后我们在把结果反转就是二叉树后续遍历的结果。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> posList = new LinkedList<>();
if (root == null)
return posList;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);//压栈
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();//出栈
posList.add(cur.val);
// 这里和前序遍历相反。先把左子树压栈在把右子树压栈。
if (cur.left != null)
stack.push(cur.left);
if (cur.right != null)
stack.push(cur.right);
}
// 遍历的结果是：根->右->左，把它反转变成：左->右->根，就是后续遍历的结果了。
Collections.reverse(posList);
return posList;
}
在来看一下后续遍历的另一种实现方式，后续遍历的顺序是[左->右->根]，就是子节点都访问完了才会访问根节点，可以看做从下往上遍历。可以参照中序遍历的访问方式，当左子节点访问完之后就会访问右子节点，右子节点访问完之后在访问当前节点，但这个时候会有个问题，就是当前节点已经出栈了，相当于当前节点搞丢了，所以在访问右子节点之前需要把当前节点在次入栈，然后在访问当前节点的右子节点，这里要注意一点的是如果右子节点已经被访问完了，就不需要在访问了，所以需要记录一下，否则会重复进入右子节点造成死循环，如下图所示，总结一下就是。
- 1，如果当前节点不为空就沿着他的左子节点一直往下走，走的时候把走过的节点全部入栈，直到没有左子节点为止。
- 2，如果当前节点为空，栈顶节点出栈。
- 3，如果出栈节点的右子树为空，或者被访问过了，说明当前子树的子节点都访问完了，直接打印这个出栈的节点值。
- 4，如果出栈节点的右子树没有被访问过，需要把出栈节点在次入栈，然后访问出栈节点的右子树，重复1,2,3,4，直到当前节点为空，或者栈为空。
这个要稍微复杂一点，关键点是要记录下已经打印过的右子树，可以使用一个变量来记录，只需要记录下打印完的子树的根节点即可。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> posList = new LinkedList<>();
if (root == null)
return posList;
Stack<TreeNode> stack = new Stack<>();
// 记录已经访问完的子树的根节点，为了防止下面访问的时候出现死循环。
TreeNode prev = null;
TreeNode cur = root;// 当前节点。
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
// 如果cur.right == prev成立，表示当前子树已经访问完了。
if (cur.right == null || cur.right == prev) {
posList.add(cur.val);
// 这里表示cur和他的子节点都已经被访问完了
prev = cur;
cur = null;
} else {
// 如果右子树没有被访问，需要把当前节点在次压栈，然后访问他的右子树。
stack.push(cur);
cur = cur.right;// 访问当前节点的右子树。
}
}
return posList;
}
后续遍历可以看做是自底往上的，只有当子节点都访问完了才应该访问当前节点，所以还可以使用一个集合 Set 来记录子节点都访问完的节点，对于子节点没被访问完的节点，先让他在次入栈然后在把他的子节点入栈，因为栈是先进后出的，如果访问到当前节点的时候他的子节点一定是都访问完了。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> posList = new ArrayList<>();
if (root == null)
return posList;
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();// 出栈。
// 如果子节点都访问完了，访问当前节点。
if (visited.contains(node)) {
posList.add(node.val);
} else {
// 如果他的子节点没访问完需要在次入栈。
stack.push(node);
// 先右子节点入栈，然后在左子节点入栈。
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
visited.add(node);// 表示两个子节点都已经入栈了。
}
}
return posList;
}
