代码随想录刷题day35|（二叉树篇）二叉树的非递归遍历（前序+后序）

目录

一、二叉树理论基础

二、非递归遍历思路

三、相关算法题目

四、总结

---

一、二叉树理论基础

详见：代码随想录刷题day34|（二叉树篇）二叉树的递归遍历-CSDN博客

二、非递归遍历思路

通过栈来模拟递归的过程。递归的本质是函数调用栈，而非递归方法则是显式地使用栈来保存待处理的节点；

初始化一个栈保存待处理的节点，初始化一个list，用来保存遍历结果，首先将根节点压入栈，之后重复以下过程：栈非空，栈顶元素出栈，添加进list，然后将出栈节点的右节点压入栈、左节点压入栈；当栈为空，说明所有节点处理完毕；

注：由于栈的先进后出，而前序遍历的顺序是中左右，所以要先压入右节点，再压入左节点，这样左节点可以先出栈；

后序遍历：左右中

前序遍历是：中左右，在前序遍历中，先将左节点压入栈，再将右节点压入栈，这样得到：中右左；最后将list反转，得到：左右中 ---> 后序遍历

三、相关算法题目

144.二叉树的前序遍历

class Solution { //非递归遍历 public List<Integer> preorderTraversal(TreeNode root) { //迭代法 Deque<TreeNode> deque = new ArrayDeque<>(); List<Integer> list = new ArrayList<>(); //deque.push(root); if(root == null){ return list; } deque.push(root); while(!deque.isEmpty()){ //list.add(deque.pop().val); TreeNode node = deque.pop(); //出栈 list.add(node.val); //添加进list //添加右孩子 添加左孩子 if(node.right != null){ deque.push(node.right); } if(node.left != null){ deque.push(node.left); } } return list; } }

 145.二叉树的后序遍历

class Solution { public List<Integer> postorderTraversal(TreeNode root) { //非递归遍历 List<Integer> list = new ArrayList<>(); Deque<TreeNode> deque = new ArrayDeque<>(); if(root == null){ return list; } deque.push(root); while(!deque.isEmpty()){ TreeNode node = deque.pop(); list.add(node.val); if(node.left != null){//先处理左节点 deque.push(node.left); } if(node.right != null){//再处理右节点 deque.push(node.right); } } //reverse(list, 0, list.size() - 1); Collections.reverse(list);//将列表反转 return list;//得到后序遍历 } } 四、总结

1.前序遍历中注意先将右子树压入栈，再压入左子树；

2.后序遍历如何在前序遍历的基础上得到；

3.list集合反转有方法直接用，Collections.reverse(list)；