2021.4.19

二叉树的遍历

 为什么要写这篇博客呢？因为我不会写迭代（
 递归的写法有手就行，这里记录遍历二叉树的两种方法：迭代法和Morris法

二叉树的迭代遍历

 递归本质上也是使用了堆栈（方法调用存储在栈区），而迭代则是显式地维护了一个栈。

 先序遍历伪代码：根→左→右

栈S;
p = root;
while(p不为null || S不空){
    while(p不为null){
        访问p节点；
        p的右子树入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
}

毕竟访问完根节点就是左子树，所以根节点和左子节点就不入栈了，而栈中存储的右子节点则表示了每次左子树访问完成后要跳转到的节点。

 中序遍历伪代码：左→根→右

栈S;
p = root;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    p = S.top 出栈;
    访问p;
    p = p的右子树;
}

每次p为null时，就找到栈顶所指的节点，因为这时栈顶节点的左子树已经访问完成了，下一个将要访问的节点就是栈顶。
我写的：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

好吧，其实和官方题解没区别。

&emsp;后序遍历伪代码：左→右→根
&emsp;方法1：先序遍历的逆序

栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的左子树入S;
        p = p的右子树;
    }
    p = S栈顶弹出;
}
结果序列逆序;

万一面试的时候碰到了这题还不让用这种方法，那就方法二
&emsp;方法二：使用访问标记
&emsp;由于对每个节点，是先访问它的左子树，再访问它的右子树，再访问它本身，但是存在一个问题：一个节点的左右子树访问完后都会返回到这个节点（栈顶为这个节点），需要在第二次返回这个节点时再访问它，可以设置一个bool型的标记，默认为false，第一次访问后将其置为true，第二次访问时发现它是true，然后才访问它。

伪代码：

栈S;
p= root;
T<节点,bool> : 节点标记;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    while(S不空 且 T[S.top] = True){
        访问S.top;
        S.top出S;
    }
    if(S不空){
        p = S.top 的右子树;
        T[S.top] = True;
    }
}

没找到java里怎么用栈存键值对，那就来个官方的阳间版本：

public static List<Integer> PostOrder(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Deque<TreeNode> sta = new LinkedList<>();
    TreeNode pre = null;//pre用于指示上一次访问的节点，和上面的访问标记异曲同工
    while (root != null || !sta.isEmpty()) {
        //惯例把左节点存一串进去
        while (root != null) {
            sta.push(root);
            root = root.left;
        }
        //先把栈顶拿出来
        root = sta.pop();
        //不存在右子树，或右子树已经访问过了
        if (root.right == null || root.right == pre) {
            list.add(root.val);
            pre = root;
            root = null;
        }
        //右子树存在且没有访问过
        else {
            sta.push(root);//栈顶放回去，下次再访问
            root = root.right;
        }
    }
    return list;
}

&emsp;总结：三种遍历都是维护了一个栈，栈中存储的节点是没有访问到的节点，且栈顶元素总为接下来要访问到的节点：先序遍历一上来就把根和左访问完了，所以栈中存储的是接下来要访问的右子节点；中序遍历先访问最左边的节点，所以栈中存储作为根节点的节点，栈顶的节点被访问并出栈后，指针转移到接下来要访问的右子树，这个右子树访问完后就是下一个栈顶元素；而后序遍历先左再右，栈中存储左右子树访问结束后的根节点。

Morris法

&emsp;不论是使用递归还是迭代，空间复杂度都是O(n)，因为都用到了栈，而这个栈最多会存储n个节点（当树是一条链的时候）。为了降低空间复杂度，可以使用Morris法对树进行遍历。

有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

&emsp;Morris法的整体思路是，对于某个节点左子树的最右叶子结点（即某个节点在中序遍历下的前驱节点），将其right设置为这个某个节点，从而利用了树中的空闲指针。
借用一下官方题解的图
&emsp;通过这种方式，在第一次访问节点时建立连接，第二次访问节点时就可以通过这些连接获得访问节点的次序，从而不再需要维护一个栈，将空间复杂度降低到了O(1)。
&emsp;建立连接的过程如下：

TreeNode p1=root,p2=null;//p1记录当前在处理的子树的根节点，p2记录这个根节点的左子节点
while (p1!=null){
    p2=p1.left;
    if(p2!=null){
        //每次找到当前节点的左子树的最右叶子结点
        while (p2.right!=null && p2.right!=p1){
            p2=p2.right;
        }
        //如果是第一次访问到这个前驱节点，则建立连接
        if(p2.right==null){
            p2.right=p1;
            //先序遍历访问节点
            p1=p1.left;
            //continue
        }
        //如果是第二次访问到这个节点，则断开连接，保持树的结构
        else if(p2.right==p1){
            //中序遍历访问节点
            p1=p1.right;
            p2.right=null;
        }
    }
    //某个子树没有左节点，则访问它的右节点
    else {
        //先序遍历访问节点
        //中序遍历访问节点
        p1=p1.right;
    }
}

&emsp;实际上理解了之后还挺简单的（先序和中序限定）

先序遍历：

public List<Integer> PreOrderMorris(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    TreeNode p1=root,p2=null;
    while (p1!=null){
        p2=p1.left;
        if(p2!=null){
            while (p2.right!=null && p2.right!=p1){
                p2=p2.right;
            }
            if(p2.right==null){
                p2.right=p1;
                list.add(p1.val);//先序遍历访问节点：第一次遇到节点
                p1=p1.left;
                //continue;
            }
            else if(p2.right==p1){
                p2.right=null;
                p1=p1.right;
            }
        }
        else {
            list.add(p1.val);//先序遍历访问节点：遇到了最左节点
            p1=p1.right;
        }
    }
    return list;
}

中序遍历：

public static List<Integer> MidOrderMorris(TreeNode root){
    List<Integer> list = new ArrayList<Integer>();
    TreeNode p1=root,p2=null;
    while (p1!=null){
        p2=p1.left;
        if(p2!=null){
            while (p2.right!=null && p2.right!=p1){
                p2=p2.right;
            }
            if(p2.right==null){
                p2.right=p1;
                p1=p1.left;
                //continue
            }
            else if(p2.right==p1){
                list.add(p1.val);//中序遍历访问节点
                //断开连接时说明这个节点的左子树已经访问完了，所以对于中序遍历而言需要访问该节点
                p1=p1.right;
                p2.right=null;
            }
        }
        else {
            list.add(p1.val);//中序遍历访问节点
            p1=p1.right;
        }
    }
    return list;
}

后序遍历：

思路借鉴：
@jason
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/

@一个Go语言全干工程师
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/