[数据结构与算法]Java 前序、中序、后序遍历二叉树的递归和迭代实现

1. 递归实现

前序遍历：中 => 左 => 右
中序遍历：左 => 中 => 右
后序遍历：左 => 右 => 中
递归实现前/中/后序遍历代码风格非常统一，写出一个其他的调调代码顺序就可以了。

前序

List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if(root == null) return res;
  
    res.add(root.val);				//	当前节点
    preorderTraversal(root.left);	//	向左递归
    preorderTraversal(root.right);	//	向右递归
    return res;
}

中序

List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) return res;
    
    inorderTraversal(root.left);
    res.add(root.val);
    inorderTraversal(root.right);
    return res;
}

后序

List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
    if(root == null) return res;
    
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    res.add(root.val);
    return res;
}

2. 迭代实现

前序

思路

1. 先将root节点入栈
2. 弹出栈顶，并将其置成当前节点
3. 依此将当前节点的右子节点、左子节点压栈（栈先入后出的性质要求先右子节点后左子节点）
4. 循环2、3直至栈空
5. 弹出的节点的值的顺序就是前序遍历的结果

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }
    return res;
}

中序

思路
由于中序遍历需要先对当前节点的左子节点进行操作，所以需要一个辅助节点cur。

1. 先将cur指向root节点
2. 如果cur不为null，cur入栈，cur指向cur的左子节点
3. 如果cur为null，cur指向栈顶并弹出，cur指向cur的右子节点
4. 循环2、3直至栈空
5. 弹出的节点的值的顺序就是中序遍历的结果

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;

    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else{
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

后序

思路
类似于前序遍历：

1. 先将root节点入栈
2. 弹出栈顶，并将其置成当前节点
3. 依此将当前节点的左子节点、右子节点压栈
4. 循环2、3直至栈空
5. 弹出的节点的值的逆序就是后序遍历的结果

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
  
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode node = stack.pop();
        res.add(0, node.val);
        if (node.left != null){
            stack.push(node.left);
        }
        if (node.right != null){
            stack.push(node.right);
        }
    }
    return res;
}