LeetCode题94，44，145，二叉树的前中后序遍历，非递归

注意：解题都要用到栈

一、前序遍历

题目要求

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

示例 4：

输入：root = [1,2]

输出：[1,2]

示例 5：

输入：root = [1,null,2]

输出：[1,2]

解题思路

我们想要用非递归的方式进行前序遍历，那么我们可以用到栈

因为遍历的值要放在链表里，所以我们先存放根节点的值，同时当前节点要放进栈里，存放完后再往左边遍历

每往左边遍历一次都要把当前根节点的值放进链表里，同时当前节点也要放进栈里

直到roo.left == null，我们就要找前一个节点的右子树为不为null，因为我们已经用栈进行存储了，所以我们可以找到前一个节点，pop一下，拿到前一个节点，再判断右子树为不为空，然后一直往回走，上述步骤，直到根节点，去判断根节点的右子树，然后也是重复上面的步骤。

代码展示

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()) {
            while(root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }

二、中序遍历

题目要求

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[1,3,2]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

解题思路

想要用非递归的思路进行中序遍历，其实步骤和前序遍历差不多

如图：

我们要先往左边找，一直找到头，同时，每遍历一个节点也要把这个节点放进栈里

直到左边节点为空，如图：

然后开始存入链表中，存入完返回上一个节点，也要存进链表中，判断该节点的右边是否为空，为空就不往右边遍历，不为空就往右边遍历，找是否又有左子树，又开始了上面的循环

，回到根节点就不说了，都是上面的这种循环。

代码展示：

public List<Integer> inorderTraversal(TreeNode root) {
        //非递归
        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.empty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }

三、后续遍历

题目要求

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

解题思路

后续遍历和前面的遍历都差不多，不过因为后序遍历的顺序是左右根，我们添加完左节点后，要判断有没有右节点，这时就不能直接弹出上一个根节点了，如果上一个节点有右节点，我们就要把这个根节点重新压栈，再去遍历右边的节点，等右边没有节点了，才开始把这个根节点存到链表中。

所以我们多定义一个前一个遍历的节点，判断右节点有没有遍历过，如果遍历过，我们就直接出栈这个节点，没有遍历过我们就要压栈这个节点，去遍历右边的节点。

代码展示

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prevAccess = null;
        while(root != null || !stack.empty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == prevAccess) {
                list.add(root.val);
                prevAccess = root;
                root = null;
            }else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }