前序、中序、后序：栈+迭代，时间O(N)，空间O(H)，H为二叉树的层高
层序：队列+迭代，时间O(N)，空间O(X)，X为某层结点数（结点最多的那一层）
先推荐更强的Morris算法，空间仅需O(1)：Morris二叉树遍历算法
前序
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>(); //链栈
stack.push(root); //根结点压栈
while(!stack.isEmpty()){ //栈内还有元素
TreeNode node = stack.pop(); //弹栈
if(node == null) continue; //栈顶为空结点
list.add(node.val); //输出
stack.push(node.right); //右孩子压栈
stack.push(node.left); //左孩子压栈，栈特性：后进先出
}
return list;
}
}
中序写法1
循环条件理解稍复杂
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>(); //链栈
while(!stack.isEmpty() || root!=null){ //栈内还有元素或root不为空
if(root!=null){ //root不为空，继续处理左子树
stack.push(root); //压栈
root = root.left; //继续处理左子树
}else{
//root为空，左子树处理完毕
TreeNode node = stack.pop(); //弹栈
list.add(node.val); //输出
root = node.right; //去右子树
}
}
return list;
}
}
中序写法2
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>(); //链栈
TreeNode node = root; //node初始指向根结点root
while(node!=null){ //将树的最左端结点全部压栈
stack.push(node); //压栈
node = node.left; //继续左孩子
}
while(!stack.isEmpty()){ //栈内还有结点
node = stack.pop(); //弹栈
list.add(node.val); //输出该结点
node = node.right; //处理右子树
while(node!=null){ //将右子树的最左端全部压栈
stack.push(node);
node = node.left;
}
}
return list;
}
}
后序
后序写法1，真后序
使用了HashSet进行标记，结点的左右子树访问完毕才输出，符合后序访问顺序
注意结点输出后要移除标记，否则最终Set会存放所有结点，使空间复杂度到O(N)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>(); //链栈
Set<TreeNode> visited = new HashSet<>(); //标记结点的左子树是否已访问
TreeNode cur = root;
while(!stack.isEmpty() || cur!=null){
if(cur==null && visited.contains(stack.peek())){
//当前结点为空，且父结点已访问，说明cur为其父结点的右孩子
visited.remove(stack.peek()); //移除该标记
list.add(stack.pop().val); //输出
}else if(cur==null){
//当前结点为空，但父节点未被访问，说明cur为其父结点的左孩子
visited.add(stack.peek()); //将cur的父结点标记为已访问
cur = stack.peek().right; //去右子树
}else{
//当前结点不为空，可以继续往左下走
stack.push(cur); //压栈
cur = cur.left; //继续处理左子树
}
}
return list;
}
}
后序写法2，假后序
为什么是假后序？
因为是使用头插法，输出结果正确，但实际遍历顺序是前序
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>(); //链栈
stack.push(root); //根结点压栈
while(!stack.isEmpty()){
TreeNode node = stack.pop(); //弹栈
if(node==null) continue; //该结点为空
stack.push(node.left); //左孩子先压栈
stack.push(node.right); //右孩子后压栈
list.add(0 , node.val); //输出，头插
}
return list;
}
}
层序：队列
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new LinkedList<>();
List<List<Integer>> res = new LinkedList<>(); //整棵树list
LinkedList<TreeNode> queue = new LinkedList<>(); //队列
queue.offer(root); //根结点入队
while(!queue.isEmpty()){ //队列不为空
List<Integer> levelList = new ArrayList<>(); //该层的list
int count = queue.size(); //该层有count个结点
for(int i=0; i<count; i++){ //i：0 -> count
TreeNode node = queue.poll(); //出队
levelList.add(node.val); //输出该结点
if(node.left!=null) queue.offer(node.left); //左孩子入队
if(node.right!=null) queue.offer(node.right); //右孩子入队
}
res.add(levelList); //将该层的list加入整棵树的list
}
return res;
}
}