二叉树的非递归遍历|前中后序遍历

二叉树的非递归遍历

前序遍历-栈

首先我们应该创建一个Stack 用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack。之后我们应该先打印左子树，然后右子树，所以先加入Stack的就是右子树，然后左子树。

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

    Stack<TreeNode> stack = new Stack<>();

    //1.根节点入栈
    stack.push(root);
    //2.栈不为空
    while (!stack.isEmpty()) {
        //2.1出栈，需暂时保存出栈元素
        TreeNode tmp = stack.pop();
        res.add(tmp.val);

        //2.2左右子树不为空的情况下，出栈元素的右子树入栈，左子树入栈
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }
    }
    return res;
}

层序遍历-队列

首先我们应该创建一个Queue用来存放节点，首先我们想要打印根节点的数据，此时Queue里面的内容为空，所以我们优先将头结点加入Queue。之后我们应该先打印左子树，然后右子树，所以先加入Queue的就是左子树，然后右子树。

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

    Queue<TreeNode> queue = new LinkedList<>();
    //1.根节点入队列
    queue.offer(root);
    //2.队列不为空
    while (!queue.isEmpty()) {
        //2.1获取当前队列的元素
        List<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            //2.1.1出队列，需暂时保存出队元素
            TreeNode tmp = queue.poll();
            level.add(tmp.val);
            //2.1.2左右子树不为空的情况下，出队元素的左子树入队，右子树入队
            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }
        }
        //2.2当前队列元素加入到res中
        res.add(level);
    }
    return res;
}

中序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树(也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层，同时在返回上层的时候已经处理完毕左子树了。

当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完 左子树->中间(就是一个节点)->右子树）

如果有右节点，其也要进行中序遍历。

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 (true) {
        //1.cur从根节点出发，一直向左保存左子树，直到cur=null
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        //2.若栈为空，退出循环
        if (stack.isEmpty()) {
            break;
        }

        //3.出栈
        TreeNode tmp = stack.pop();
        res.add(tmp.val);

        //4.cur指向出栈元素的右子树，
        //若为空则继续出栈，若不为空再继续向左保存子树
        cur = tmp.right;
    }
    return res;
}

后序遍历-栈

同理创建一个 Stack。

尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素。

该元素无右子树，或者右子树已经访问过，则可以处理该元素，并用prev记录当前已处理的元素

否则访问右子树，进行后序遍历

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

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (true) {
            //1.cur从根节点出发一直向左保存左子树，直到cur=null
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            //2.若栈为空，退出循环
            if (stack.isEmpty()) {
                break;
            }

            //3.得到栈顶元素，先不访问（满足条件才可以访问）
            TreeNode tmp = stack.peek();

            //4.若栈顶元素无右子树或者右子树已被访问，则可以访问
            //若prev==tmp.right，则tmp一定是其右子树的根节点。因为此时右子树已访问完毕
            if (tmp.right == null || tmp.right == prev) {
                stack.pop();
                res.add(tmp.val);
                prev = tmp;
            } else { //5.cur指向栈顶元素的右子树
                cur = tmp.right;
            }
        }
        return res;
    }