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;}