二叉树的遍历（非递归）

前序遍历

遵从 根左右 遍历，结果为：GDAFEMHZ
二叉树前序非递归遍历使用到的是栈，先加入右节点，再加入左节点。

public List<Node> preorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList();
        List list = new ArrayList();
        LinkedList stack = new LinkedList();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }

中序遍历

遵从 左根右 遍历，结果为：ADEFGHMZ
二叉树中序非递归遍历使用到的是栈。需要一个临时的cur变量

public static List<Node> inOrder(Node root){
        if (root == null) {
            return new ArrayList<>();
        }
        List<Node> list = new ArrayList<>();
        LinkedList<Node> stack = new LinkedList<>();
        Node cur = root;
        while(!stack.isEmpty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node node = stack.pop();
            list.add(node);
            if(node.right != null) {
                cur = node.right;
            }
        }
        return list;
    }

后序遍历

遵从 左右根 遍历，结果为：AEFDHZMG
二叉树后序非递归遍历使用到的是栈。需要一个临时的cur变量。

public static List<Node> postOrder(Node root){
        if(root == null) return new ArrayList<>();
        List<Node> list = new ArrayList<>();
        LinkedList<Node> stack = new LinkedList<>();
        Node cur = root;
        stack.push(cur);
        while(!stack.isEmpty()) {
            Node node = stack.peek();
            if(node.left != null && node.left != cur && node.left != cur) {
                stack.push(node.left);
            }else if(node.right != null && node.right != cur) {
                stack.push(node.right);
            }else {
                list.add(stack.pop());
                cur = node;
            }
        }
        return list;
    }

层序遍历

遵从 左右根 遍历，结果为：GDMAFHZE
二叉树的层序遍历使用的是队列。

public static List<Node> cengOrder(Node root){
        if(root == null) return new ArrayList<>();
        List<Node> list = new ArrayList<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            list.add(node);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
        return list;
    }

结束，必须掌握的知识，背也要背下来。