代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

二叉树的迭代遍历(不使用递归实现遍历)

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，递归是通过栈实现的，自然也可以直接通过栈实现对二叉树的遍历。

144.二叉树的前序遍历

二叉树在树中前序遍历是中左右，使用迭代遍历每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。要先加入 右孩子，再加入左孩子，是因为基于栈先进后出的特性，这样出栈的时候才是中左右的顺序。（中间节点出栈才压入左右节点）

使用迭代法的前序遍历代码示例:

public List<Integer> preorderTraversal(TreeNode root) {//初始化：栈，列表，根入栈List<Integer>res=new ArrayList<>();Stack<TreeNode>stack=new Stack<>();//根为空if(root==null)return res;//根不为空stack.push(root);while(!stack.isEmpty()){TreeNode node=stack.pop();res.add(node.val);if(node.right!=null)stack.push(node.right);if(node.left!=null)stack.push(node.left);}return res;}

94.二叉树的中序遍历

二叉树的中序遍历是左中右，二叉树的中序遍历不能像二叉树的前序遍历和后序遍历一样，因为二叉树的中序遍历的访问顺序（对节点的遍历）和处理顺序（将节点值加入到结果数组中）不相同，所以需要使用其他方法。使用一个指针来控制访问和处理。对于每个树（子树）的根结点，先不断向左访问，将路径上的元素压入栈中，直到到达null再开始处理，将null的上一个访问的节点数据存入结果数组，将指针指向该结点的右节点。

使用迭代法实现的中序遍历示例：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();if(root==null)return res;Stack<TreeNode>stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){if(cur!=null){stack.push(cur);cur=cur.left;}else{cur=stack.pop();res.add(cur.val);cur=cur.right;}}return res;}

​​​​​​​​​​​​​​145.二叉树的后序遍历

二叉树的后序遍历是左右中，二叉树在树中前序遍历是中左右，在使用迭代遍历时，只需要基于前序遍历，将左右节点的顺序交换，然后再将结果数组反转就可以了。

使用迭代法的后续遍历示例：

public List<Integer> postorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();if(root==null)return res;Stack<TreeNode>stack=new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node=stack.pop();res.add(node.val); if(node.left!=null) stack.push(node.left);if(node.right!=null) stack.push(node.right);}Collections.reverse(res);return res;}