【强基计划】LeetCode—二叉树的前、中、后序的非递归实现

✨哈喽，进来的小伙伴们，你们好耶！✨

🍅🍅系列专栏:【强基计划】

✈️✈️本篇内容: 二叉树的前、中、后序的非递归实现！

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

🍱🍱码云存放仓库gitee：Java数据结构代码存放！

一、二叉树的前序遍历

给你二叉树的根节点

root

，返回它节点值的 前序* *遍历。

示例 1：

问题分析：

那么通过前面的二叉树的学习，博主已经介绍过二叉树的前 中 后序的递归实现代码，看起来是非常的简单，那么，对于二叉树的遍历，还存在它的非递归实现，也就是所谓的迭代，那么本题博主就将演示如何使用迭代来解决这个问题！

我们可以看到问题要求就是一个前序遍历，那么前序遍历的概念就是依据根、左、右的顺序来访问每个节点，那么本题也一样，我们可以定义一个栈存放每个遍历到的节点，然后出栈打印该节点的值，同时我们定义一个ArrayList来存放我们的节点的val，当我们遇到叶子节点比如图中的D时，那么我们的cur此时应该等于E，下面看具体的实现方法！

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
   public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                ret.add(cur.val);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            cur = top.right;
        }
        return ret;
    }
}

代码分析：

这里的双层循环就是因为当我们遍历到叶子节点，想执行代码的这两行时：TreeNode top = stack.pop(); cur = top.right;发现这两行代码不在我们的循环里面，那么这个程序就无法完成前序遍历，那么前序遍历的非递归实现难就难在这里，那么怎么办呢？可以看到，我们在代码中又加了一个判断循环的条件，就是这一行：while (cur != null || !stack.isEmpty())，就是当我们的栈不为空的时候，我们让cur = cur.right；这样就能实现遍历到右子树，从而遍历到所有节点。

OK,那么学会了我们的前序遍历，相信聪明的你肯定就自然而然的能理解二叉树的中、后序遍历的非递归实现，那么这里就奉上实现代码，实现原理都是一样的，博主这里就不过多阐述啦！

二、二叉树的中序遍历

给定一个二叉树的根节点

root

，返回 它的 中序 遍历 。

示例 1：

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            ret.add(top.val);
            cur = top.right;
        }
        return ret;
    }
}

三、二叉树的后序遍历

给你一棵二叉树的根节点

root

，返回其节点值的 **后序遍历 **。

示例 1：

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        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) {
                ret.add(top.val);
                stack.pop();
                prev = top;
            } else {
                cur = top.right; 
            }
        }
        return ret;
    }
}

好啦，那么今天的内容分析就到这里了，感谢你的阅读，后期会持续输出数据结构的相关知识点，期待你的一键三连！