非递归方式实现二叉树的前、中、后序遍历

飞熊 • 2023年12月26日下午1:22 • 技术随笔 • 阅读 194

各位朋友们，大家五一快乐，今天我为大家分享的是不用递归的方式实现二叉树的前、中、后序遍历，一起来看看吧。

文章目录

二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历

二叉树的前序遍历

虽然我们说的是不用递归的方式实现，但是我们的思路还是模拟递归的实现，那么我们如何不用递归来模拟实现递归呢？我们要想模拟递归，我们需要知道实现递归的底层逻辑是什么？递归实际上是通过栈这个数据结构来实现的，我们都知道递归的顺序是先完成后递归的，这也就跟栈先进后出的原理是类似的，所以我们想模拟递归，也需要借用栈这个数据结构。

在知道了原理之后，我们接下来就需要知道怎么样来实现了，因为这里是前序遍历，先遍历根节点，然后是左子树，最后是右子树，所以我们先遍历左子树，并且在遍历的同时我们将遍历的节点存储在栈中并打印，方便我们找到节点的右子树。当我们的root遍历到为null时，就说明左树遍历完了，我们就将栈顶的节点弹出，将root等于弹出节点的右子树，直到root等于null并且栈为空时完成遍历。

节点6的右树也为null，所以我们弹出栈顶的元素，cur = top.right，继续上面操作。

public void preOrderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                System.out.println(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

二叉树的中序遍历

中序遍历的思路跟前序遍历的思路是一样的，只是打印的顺序不同，我们在从栈中弹出节点的同时打印。

public void inOrderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val);
            cur = top.right;
        }
    }

二叉树的后序遍历

后序遍历的思路跟前序和中序的思路是不同的，我们需要判断什么时候该打印，因为是后序遍历，所以我们需要在遍历完右树或者右树为null的时候在遍历根节点。

public void postOrderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                System.out.println(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }