刷算法Leetcode---7（二叉树篇）（前中后序遍历）

前言

        本文是跟着代码随想录的栈与队列顺序进行刷题并编写的 代码随想录

        好久没刷算法了，最近又开始继续刷，果然还是要坚持。

        二叉树的题目比之前多了好多，就多分几次写啦~

        这是力扣刷算法的其他文章链接：刷算法Leetcode文章汇总

二叉树篇（前中后序遍历）

（1）144.二叉树的前序遍历

        ①递归，先加入当前节点值，再递归左右子节点

        ②栈迭代，先获取当前节点值，注意右节点先入栈，左节点后入栈

        ③栈迭代，从根开始遍历左节点，取值并入栈，再取栈顶右节点重复

        ④Morris遍历，将左节点的最右节点（即p2）右指针指向根，不使用额外空间，实现左子树遍历完后就回到根遍历右子树。若p2右指针为空，代表该树（即p1）的左子树未遍历

        核心思想：添加根p1的值（即为中），遍历左节点，左不空就添加指向根的指针并继续往左，左空就添加该节点值（即为左）并找右节点，若右节点不为根就作为新子树遍历（即为右），若为根就回到之前的树遍历右节点并添加

class Solution {private List<Integer> res;public List<Integer> preorderTraversal(TreeNode root) {res = new ArrayList<>();TreeNode p1 = root, p2 = new TreeNode();while(p1!=null){if(p1.left==null){res.add(p1.val);p1=p1.right;}else{p2=p1.left;while(p2.right!=null&&p2.right!=p1){p2=p2.right;}if(p2.right==null){p2.right=p1;res.add(p1.val);p1=p1.left;}else{p2.right=null;p1=p1.right;}}}return res;}
}

（2）145.二叉树的后序遍历

        ①递归，先递归左右子节点，再加入当前节点值

        ②栈迭代，取栈头，左右节点依次入栈，栈头值头插到结果

        ③Morris遍历，核心思路还是创建一个右子树最后一个节点到根的指针，由于根节点最后添加，要实现一个左节点到最右节点添加的方法

        核心思想：从根p1开始，左不空就添加指向根的指针并继续往左，左空就添加（即为左）并遍历右节点，右不为根就作为新树遍历左节点，右为p1就代表所有左节点遍历完，将p1左节点到p2的节点逆序添加（即为右+中），注意最后要将根到整棵树最右节点的路径逆序添加

class Solution {private List<Integer> res;public List<Integer> postorderTraversal(TreeNode root) {res = new ArrayList<>();TreeNode p1=root,p2=null;while(p1!=null){if(p1.left==null){p1=p1.right;}else{p2=p1.left;while(p2.right!=null&p2.right!=p1){p2=p2.right;}if(p2.right==null){p2.right=p1;p1=p1.left;}else{p2.right=null;addRightPath(p1.left);p1=p1.right;}}}addRightPath(root);return res;}private void addRightPath(TreeNode node){int p = res.size();while(node!=null){res.add(p,node.val);node=node.right;}}
}

（3）94.二叉树的中序遍历

        ①递归，先递归左子树，再加入当前节点值，再递归右子树

        ②栈迭代，一直找到最左节点并依次入栈，此时栈顶值加入结果，并将右节点作为当前节点，当栈或当前节点都不空时进行循环（注意是或）

        注意：由于中序遍历要将根节点记录的中间，没办法像前序或后序实现简洁的迭代，必须先将左子树遍历完

        ③Morris遍历，与之前遍历思路同，创建一个右子树最后一个节点到根的指针。先将左子树遍历完（即左）后再添加根节点（即中），再遍历右子树（即右）。

class Solution {private List<Integer> res;public List<Integer> inorderTraversal(TreeNode root) {res = new ArrayList<>();TreeNode p1=root,p2=null;while(p1!=null){if(p1.left==null){res.add(p1.val);p1=p1.right;}else{p2=p1.left;while(p2.right!=null&&p2.right!=p1){p2=p2.right;}if(p2.right==null){p2.right=p1;p1=p1.left;}else{p2.right=null;res.add(p1.val);p1=p1.right;}}}return res;}
}

二叉树篇（前中后序遍历）总结

        ①区分三种遍历顺序，前序（根左右）中序（左根右）后序（左右根），指的是根的位置

        ②都有递归实现的方法，代码简洁易懂，只用注意根添加和左右子树递归的顺序即可

        ③都有迭代实现的方式，需要显式栈辅助。都可以先将左子树全遍历完再遍历右子树，需要两层while。其中前序和后序有较简洁的迭代，每次将左右节点按特定顺序入栈即可，而中序遍历一定要先遍历完左子树才行

        ④都有Morris遍历，特点在于将左节点的最右节点右指针指向根节点，从而实现左子树遍历完后回到根节点遍历右子树，节点添加顺序有不同。特别是后序遍历对最右路径节点的单独添加，最好自己调试一遍更容易理解

        ⑤一般来说能用递归实现，就能用栈实现，因为递归是隐式栈

        ⑥代码随想录中有一种二叉树的统一迭代法，对前中后序的迭代遍历使用几乎相同的算法，只修改栈的添加顺序，感兴趣可以看一下，我记不下来就没看