二叉树的几种非递归遍历

二叉树的几种非递归遍历解法

二叉树的递归遍历想必了解递归以及二叉树的同学都能够轻松写出正确答案，然而二叉树的非递归遍历确是很多人难以理解学会的，所以我在这里进行一下归纳总结，主要是复习巩固一下这方面的知识。

非递归先序遍历

思路

• 首先将根节点入栈
• 然后循环判断栈不为空
• 则弹出栈顶元素
• 如果弹出元素的右子树不为空则入栈
• 如果弹出元素的左子树不为空则入栈
• 继续循环

解析：由于先序遍历为[根-左-右]，所以根节点应该先入栈，然后出栈的同时依次入栈右-左子树即可。

代码

public static void frontPrintByLoop(TreeNode root) {
    if (root != null) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " | ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
}

非递归中序遍历

思路

• 首先将根节点入栈
• 循环判断根节点是否有左子树，有则入栈继续循环，否则循环结束
• 然后循环判断栈不为空
• 则弹出栈顶元素
• 如果栈顶元素右子树不为空
• 则循环入栈右子树及其右子树的左子树
• 继续循环

解析：因为中序遍历为[左-根-又]，所以树的左子树应该先入栈，循环入栈左子树之后循环出栈，出栈的同时判断出栈元素是否有右子树，如果右子树不为空则对右子树执行相同的操作，即入栈右子树的左子树。

代码

public static void midPrintByLoop(TreeNode root) {
    if (root != null) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(node);
        while (node.left != null) {
            stack.push(node.left);
            node = node.left;
        }
        while (!stack.isEmpty()) {
            node = stack.pop();
            TreeNode n = node.right;
            while (n != null) {
                stack.push(n);
                n = n.left;
            }
            System.out.print(node.val + " | ");
        }

    }
}

非递归后序遍历

思路 1

• 逆向思考先序遍历，因为后序遍历为[根-左-右]，我们可以以类似先序遍历的方式先将[右-左-根]的顺序找出来存入另一个栈，然后再依次出栈该栈元素即可

代码 1

public static void lastPrintByOtherStack(TreeNode root) {
    if (root != null) {
        final Stack<TreeNode> stack = new Stack<>();
        final Stack<TreeNode> stackReverse = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                stackReverse.push(node);
                if (node.left != null) {
                    stack.push(node.left);
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
            }
        }
        while (!stackReverse.isEmpty()) {
            TreeNode node = stackReverse.pop();
            System.out.print(node.val + " | ");
        }
    }
}

思路 2

• 只使用一个栈
• 先将根节点入栈
• 设置一个标识引用 h首先指向root
• 循环判断栈非空
• 在循环中判断栈顶元素node
• 如果node左子树不为空并且左右子树都不为h指向的元素
• 入栈左子树
• 否则再判断右子树是否为空以及右子树是否为h节点
• 入栈右子树
• 否则，弹出栈顶元素，并且将h指向该弹出的栈顶元素

代码 2

public static void lastPrintByOneStack(TreeNode root) {
    if (null != root) {
        TreeNode h = root;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(h);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node.left != null && node.left != h && node.right != h) {
                stack.push(node.left);
            } else if (null != node.right && node.right != h) {
                stack.push(node.right);
            } else {
                node = stack.pop();
                System.out.print(node.val + " | ");
                h = node;
            }
        }
    }
}

解析：使用一个栈进行后序遍历的时候需要使用一个h引用来标识上一个节点是否被遍历过，是的话就往上判断之后的树节点即可。

按层遍历二叉树

思路

以上前中后序遍历二叉树都是用到了栈这种数据结构，而按层遍历二叉树就非常简单了，只需要引入先入先出的队列，然后依次在出队的时候将出队元素的左右子树入队即可。

• 根节点入队
• 队列不为空则开始循环
• 如果队首元素左子树不为空，就入队
• 右子树不为空，也入队
• 队首元素出队输出

代码

public static void levelPrintOutTree(TreeNode root) {
    if (null != root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode i = root;
        while (!queue.isEmpty()) {
            if (i.left != null) {
                queue.add(i.left);
            }
            if (i.right != null) {
                queue.add(i.right);
            }
            System.out.print(i.val + " | ");
            queue.poll();
            i = queue.peek();
        }
    }
}