刷算法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;
    }
}