临朐网站建设价格怎么查询搜索关键词
注意：解题都要用到栈
一、前序遍历
题目要求
给你二叉树的根节点
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;}