数据结构之morris遍历
morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
时间复杂度：O(n)
额外空间复杂度：O(1)在你阅读以下代码之前，在这边先讲解一下Morris的通用解法过程。
在详细了解morris遍历之前我们先了解一下m orris遍历的基本流程是什么：
当前节点cur一开始来到整颗树的头
1.如果cur没有左树则cur=cur->right;即cur向右移动
2.如果cur有左树则找到左树的最右节点记为mostRight
2.1如果mostRight的右指针指向空（nullptr)则让mostRight指向当前节点，cur=cur->left即cur向左移动。
2.2mostRight的右指针指向当前节点则将mostRight的右指针指向空（nullptr),然后cur=cur->right即cur向右移动。
3.当cur来到空时结束即cur==nullptr.
可能很多老铁有点儿迷我们下面看一个例子相信老铁们就明白了
首先我们先来看整棵树的morris序老铁们先忘掉前中后序
首先cur来到头节点也就是1这个节点按照上面的流程我们首先看有没有左子树在这里很明显是有的。则我们找到左子树 的最右节点mostRight也就是5节点我们发现他的右指针是指向空的则我们将其指向当前节点cur也就是1这个节点。然后cur向左移动来到2这个节点再检查他有没有左树我们发现他是有的，则我们找到他的左子树的最右节点也就是4这个节点我们可以发现4这个节点右指针是指向空的，则我们将其右指针指向当前节点也就是2这个节点，cur=cur->left.cur向左移动来到了4这个节点。我们发现4这个节点没有左子树则cur=cur->right。cur向右移动来到2这个节点再找到他左树的最右节点我们可以发现mostRight这个节点指向了当前节点那么我们将其右指针指向空，然后cur向右移动。重复上述步骤就可以得到morris序。即：1 2 4 2 5 1 3 6 3 7
有的老铁可以就有疑惑了这样时间复杂度还是0（N）吗？答案是的时间复杂度仍然是0(N)
这是为什么呢？首先每一个节点都要遍历到这是少不了的其次是在morris遍历中如果一个节点有左树那么要遍历左树的右边界
比如说值为1的节点左树的右边界是 2 5 .节点2左树的右边界为 4 节点 3 的左树的右边界为 6我们发现一次遍历左树右边界的代价最多为0（N）在morris遍历中我们只要遍历二次左树右边界也就是0(2*N）也就是0（N）
下面我们来看遍历的代码：
TreeNode*cur=root; TreeNode*mostRight=nullptr; while(cur){ mostRight=cur->left; if(mostRight){//判断左树是否为空 while(mostRight->right&&mostRight->right!=cur){//如果最左节点右指针指向空或者当前节点就停下来 mostRight=mostRight->right; } if(mostRight->right==nullptr){//如果为空就将其指向当前节点 ans.push_back(cur->val); mostRight->right=cur; cur=cur->left; continue; }else{//等价于mostRight->right=cur; mostRight->right=nullptr;//将其指向空 } //向右移动合并了 } cur=cur->right;//为空则往右移动 }
我们如何从morris遍历中得到先序中序和后序遍历了？先序和中序很容易就得到了我们先来看中序遍历
1.如果这个节点是第一次来到它我们就输出它即可第二次来到它不输出它
对应代码：
vector<int> preorderTraversal(TreeNode* root) { vector<int>ans; if(!root)return ans; TreeNode*cur=root; TreeNode*mostRight=root; while(cur){ mostRight=cur->left; if(mostRight){ while(mostRight->right&&mostRight->right!=cur){ mostRight=mostRight->right; } if(mostRight->right==nullptr){ //第一次来到它 ans.push_back(cur->val); mostRight->right=cur; cur=cur->left; continue; }else{ mostRight->right=nullptr; } } else{ //第一次来到也就是没有左树ans.push_back(cur->val); } cur=cur->right; } return ans; }
中序遍历：
1.如果一个节点如果能够来到两次的节点第二次打印。
2.对于只能来到一次的节点直接打印
这里值得注意的是：morris遍历会来到一个左孩子不为空的结点两次，而其它结点只会经过一次。因此使用morris遍历打印先序序列时，如果来到的结点无左孩子，那么直接打印即可（这种结点只会经过一次），否则如果来到的结点的左子树的最右结点的右孩子为空才打印（这是第一次来到该结点的时机），这样也就忽略了
cur经过的结点序列中第二次出现的结点；而使用morris遍历打印中序序列时，如果来到的结点无左孩子，那么直接打印（这种结点只会经过一次，左中右，没了左，直接打印中），否则如果来到的结点的左子树的最右结点不为空时才打印（这是第二次来到该结点的时机），这样也就忽略了cur经过的结点序列中第一次出现的重复结点。
对应代码：
vector<int> inorderTraversal(TreeNode* root) { vector<int>ans; if(!root)return ans; TreeNode*cur=root; TreeNode*mostRight=nullptr; while(cur){ mostRight=cur->left; if(mostRight){ while(mostRight->right&&mostRight->right!=cur){ mostRight=mostRight->right; } if(mostRight->right==nullptr){ mostRight->right=cur; cur=cur->left; continue; }else{ mostRight->right=nullptr; } } ans.push_back(cur->val); cur=cur->right; } return ans; }
后序遍历：
后序遍历就有一点小难了基本操作是
1.只输出能够回到自己两次的节点并且是在第二次输出并且输出的不是自己而是它的左树的右边界逆序打印
2.最后打印整颗树的右边界逆序打印
对w
lass Solution { public: vector<int>ans; //反转 TreeNode*reverseEdge(TreeNode*root){ TreeNode*pre=nullptr; TreeNode*next=nullptr; while(root){ next=root->right; root->right=pre; pre=root; root=next; } return pre; } //打印边界 void printEdge(TreeNode*root){ TreeNode*tail=reverseEdge(root); TreeNode*cur=tail; while(cur){ ans.push_back(cur->val); cur=cur->right; } reverseEdge(tail); } vector<int> postorderTraversal(TreeNode* root) { TreeNode*cur=root; TreeNode*mostRight=nullptr; while(cur){ mostRight=cur->left; if(mostRight){ while(mostRight->right&&mostRight->right!=cur){ mostRight=mostRight->right; } if(mostRight->right==nullptr){ mostRight->right=cur; cur=cur->left; continue; }else{ mostRight->right=nullptr; printEdge(cur->left);//第二次输出左树右边界 } } cur=cur->right; } printEdge(root);//打印整颗树的右边界 return ans; } };
我们来利用morris遍历来解决一些问题
验证二叉搜索树：
对应letecode链接：
题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
解题思路：
在前面二叉树树概念的博客中已经提到了利用二叉搜索树的中序遍历是有序的因此我们只需要定义一个变量prev记录前一个节点 ，和当前节点做比较如果当prev对应节点的值大于当前节点的值则为false变量结束之后如果不是false那么就是true;
对应代码：
class Solution { public: bool isValidBST(TreeNode* root) { if(!root)return true; TreeNode*cur=root; bool res=true; TreeNode*prve=nullptr;//记录前一个节点 TreeNode*mostRight=nullptr; while(cur){ mostRight=cur->left; if(mostRight){ while(mostRight->right&&mostRight->right!=cur){ mostRight=mostRight->right; } if(mostRight->right==nullptr){ mostRight->right=cur; cur=cur->left; continue; }else{ mostRight->right=nullptr; } } if(prve&&prve->val>=cur->val){ res=false; } cur=cur->right; } return res; } };