写在前面

这种题回过头来再做一下，别有一番风味。之前没看过题解中的 Morris 遍历方法，只是简单的AC然后下一题，可能也不是很明所以然，借此记录一下 Morris 遍历（好像是KMP中的M）。

递归遍历一遍与迭代

根据前序遍历的特点，很容易写出前序遍历的思路，就是打印当前值，然后遍历其左右子树，其中的栈是由系统自动维护的。

  • 遍历的过程中同时写入相应的元素值，因此该递归函数是不需要返回值的，那就说明它需要传入参数（不设置全局变量的话）
  • void traverse(TreeNode* root,vector<int> & res)
{
    if(root==nullptr)
        return;
    res.push_back(root->val);
    traverse(root->left,res);
    traverse(root->right,res);
}

  • 与迭代的区别： 需要自己显式的维护一个栈，其实也就是在遍历到当前节点时，在写入该元素值时，将结点入栈，等需要它的时候再出栈（左孩子为空），进行右子树的处理。

分解成子问题的递归

前序遍历的思路也可以这样理解，就是将该节点、该节点左孩子的前序遍历、该节点右孩子的前序遍历拼接起来，是不是就可以通过分解成子任务来完成。

  • 对于递归函数，一定要写清楚三要素：终止条件、传入参数、返回值

  • 很明显：对于分解子问题是需要有返回值，因为对于根节点，它需要整合来自左右子树的前序遍历。

    // 返回值类型及传入参数类型
vector<int> traverse(TreeNode* root)
{   
    // 终止条件
    if(root==nullptr)
        return {};
    vector<int> left=traverse(root->left);
    vector<int> right=traverse(root->right);
    vector<int> res={root->val};
    res.insert(res.end(),left.begin(),left.end());
    res.insert(res.end(),right.begin(),right.end());
    return res;
}

Morris 遍历

看了一些介绍，Morris遍历就是在将树进行线索化，其实之前的递归利用栈的特性也是一种线索化，具体来说就是栈里面保存了下一步需要访问的点。因为前序遍历直观上来看是从上一直往左下角遍历，然后遇到空指针回溯遍历右侧；栈中其实就是保存了线索化的信息。Morris遍历就是利用其中的空指针来减少内存空间使用，利用这些将这棵树线索化。

如何线索化与去线索化

结合这个视频和官方解答，可以快速的了解它是如何线索化以及去线索化的，视频来源。

线索化具体来说：

其实就是要明白什么时候需要用到栈中节点的信息（栈不存在，利用线索化信息找到）

  • 对于当前节点p：其实就是当该节点的左孩子（如果存在）的右子树遍历完了就会用到当前节点 p 的信息。这就对应 官解 中所描述的：在当前节点的左子树中找到当前节点在中序遍历下的前驱节点 Q；因为该节点（Q节点）遍历完后就会用到当前节点（p节点）的右子树信息。

去线索化具体来说：

其实对于有左子树的点，它会被遍历两次，一次是入栈前，另外一次是“栈内弹出”的；前者是发生在遍历左子树之前，后者发生在遍历左子树之后。如果发生在之前，则需要将其线索化，反之则需要将其去线索化，将二叉树还原。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr)
            return {};
        vector<int> ans;
        TreeNode* p1=root;
        TreeNode* p2=nullptr;
        while(p1!=nullptr)
        {
            p2=p1->left;
            // 先进行线索化
            if(p2!=nullptr)
            {
                // 找到当前节点p1的中序遍历的前驱节点，其实就是p1左子树的最右节点
                while(p2->right!=nullptr && p2->right!=p1)
                {
                    p2=p2->right;
                }
                // 如果因为p2->right为空，则说明还没有线索化
                if(p2->right==nullptr)
                // 没有线索化则构建线索化
                {
                     p2->right=p1;
                     // 写入当前值
                     ans.push_back(p1->val);
                     // 索引左子树
                     p1=p1->left;
                     // 避免索引右子树
                     continue;
                }
                else
                // 如果有，说明左侧已经访问过，则断开该线索
                p2->right=nullptr;
            }
            else
            {   
                // 左子树为空则直接写入数值
                ans.push_back(p1->val);
            }
            // 遍历右子树
            p1=p1->right;
        }
        return ans;
    }
};

$\cdots$ end $\cdots$