二叉树遍历有很多种，下面介绍几种常见的遍历方式。
给定树的节点为
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
先序：1 2 4 6 7 8 3 5
中序：4 7 6 8 2 1 3 5
后序：7 8 6 4 2 5 3 1
1.先序遍历
根节点->左子树->右子树（根->左->右）
public static void preorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<>();
TreeNode node = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
System.out.print(node.val + " ");
treeNodeStack.push(node);
node = node.left;
}
if (!treeNodeStack.isEmpty()) {
node = treeNodeStack.pop();
node = node.right;
}
}
}
递归方式
public static void recursionPreorderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
recursionPreorderTraversal(root.left);
recursionPreorderTraversal(root.right);
}
}
2.中序遍历
左子树->根节点->右子树（左->根->右）
public static void middleorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<>();
TreeNode node = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
if (!treeNodeStack.isEmpty()) {
node = treeNodeStack.pop();
System.out.print(node.val + " ");
node = node.right;
}
}
}
递归方式
// 递归中序遍历
public static void recursionMiddleorderTraversal(TreeNode root) {
if (root != null) {
recursionMiddleorderTraversal(root.left);
System.out.print(root.val + " ");
recursionMiddleorderTraversal(root.right);
}
}
3.后序遍历
左子树->右子树->根节点（左->右->根）
后续遍历和先序、中序遍历不太一样。
后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。
所以需要设置一个lastVisit游标。
若lastVisit等于当前考查节点的右子树，表示该节点的左右子树都已经遍历完成，则可以输出当前节点。
并把lastVisit节点设置成当前节点，将当前游标节点node设置为空，下一轮就可以访问栈顶元素。
否者，需要接着考虑右子树，node = node.right。
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
//查看当前栈顶元素
node = treeNodeStack.peek();
//如果其右子树也为空，或者右子树已经访问
//则可以直接输出当前节点的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
//否则，继续遍历右子树
node = node.right;
}
}
}
递归方式
// 递归后序遍历
public static void recursionPostorderTraversal(TreeNode root) {
if (root != null) {
recursionPostorderTraversal(root.left);
recursionPostorderTraversal(root.right);
System.out.print(root.val + " ");
}
}
4.广度优先遍历
广度优先遍历，是指从上至下逐层访问，又称层次遍历。每一层从左至右访问，该层结束后进入下一层访问，直至没有节点为止。
以下展示广度优先遍历，利用了Java的Queue队列先进先出的特性：
public static void broadFirstSearch(Tree tree) {
Queue<Tree> queue = new LinkedList<>();
queue.add(tree);
while (!queue.isEmpty()) {
Tree node = queue.poll();
System.out.print(node.data + " ");
// queue先进先出，所以先左后右
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
System.out.println();
}
5.总结
二叉树遍历最基本的几种方式。剩下的基本上都是基于这几种方式进行的变种。比如Z字行遍历，取二叉树第K大的元素等。熟练掌握遍历过程即可解决大部分遍历问题。
例：
public static TreeNode getNum(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
int index = 0;
TreeNode tmpNode = root;
while (tmpNode != null || !stack.empty()) {
while (tmpNode != null) {
stack.push(tmpNode);
tmpNode = tmpNode.right;
}
if (!stack.isEmpty()) {
TreeNode node = stack.pop();
index++;
tmpNode = node.left;
if (index == k) {
return node;
}
}
}
return null;
}
参考