一、二叉树的三种遍历方式
二叉树的遍历主要有三种：先(根)序遍历（根左右），中(根)序遍历（左根右），后(根)序遍历（左右根），以下图为例分别说明。
1、先(根)序遍历（根左右）
先序遍历的原则是：先根、再左、再右。
即：ABCDEFGH
2、中(根)序遍历（左根右）
中序遍历的原则是：先左、再根、再右。
即：BDCEAFHG
3、后(根)序遍历（左右根）
后序遍历的原则是：先左、再右、再根。
即：DECBHGFA
二、代码实现二叉树的三种遍历方式
/**
* 下文中用到的TreeNode类
*/
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
1、递归方式实现
/**
* 先序遍历的原则是：先根、再左、再右。
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
if(root != null){
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
}
/**
* 中序遍历的原则是：先左、再根、再右
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
if(root != null){
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}
/**
* 后序遍历的原则是：先左、再右、再根
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
if(root != null){
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}
2、迭代方式实现
/**
* 先序遍历的原则是：先根、再左、再右。
* 1.辅助变量 tempNode 初始化为根节点
* 2.当 tempNode != null 时，就保存这个节点值到 list 中，然后将其入栈并置 tempNode为它自己的左子节点
* 3.当 tempNode == null 时，说明已经遍历到二叉树的左下节点了，这时前序遍历应该遍历右子树了，首先 pop 出已经遍历保存过的父节点，然后置 tempNode 为 pop 出的父节点的右子节点
* @param root
* @param list
*/
private void preorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
list.add(tempNode.val);
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
tempNode = tempNode.right;
}
}
}
/**
* 中序遍历的原则是：先左、再根、再右
* 1.辅助变量 tempNode 初始化 root
* 3.当栈非空或 tempNode 非 null 时，循环
* 3.1 tempNode != null 时，说明还有左子节点存在，将 tempNode 入栈，并且将 tempNode 置为它自己的左子节点
* （和前序遍历的区别在于这里遍历到先不保存到 list 中，出栈的时候再将其保存到 list 中）
* 3.2 tempNode == null 时，说明到二叉树左下的节点了，这时栈顶的父节点出栈赋值给 tempNode ，并保存节点值到 list ，将 tempNode 置为栈顶节点的右子节点继续循环
* @param root
* @param list
*/
private void inorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while(!stack.isEmpty() || tempNode != null){
if (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
} else {
tempNode = stack.pop();
list.add(tempNode.val);
tempNode = tempNode.right;
}
}
}
/**
* 后序遍历的原则是：先左、再右、再根
* 1.对应前序遍历的反操作：
* 2.前序遍历从尾部添加元素，后序遍历从头部添加元素
* 3.前序遍历去左子树，后序遍历去右子树
* @param root
* @param list
*/
private void postorder(TreeNode root, List<Integer> list){
Stack<TreeNode> stack = new Stack<>();
TreeNode tempNode = root;
while (!stack.isEmpty() || tempNode != null) {
if (tempNode != null) {
stack.push(tempNode);
list.add(0, tempNode.val);
tempNode = tempNode.right;
} else {
tempNode = stack.pop();
tempNode = tempNode.left;
}
}
}
