使用递归和栈遍历二叉树，空间复杂度都是O(n)，而Morris遍历通过使用叶子结点的null指针标记前驱结点，使空间复杂度降为了O(1)。
中序遍历：左子树-根节点-右子树 所以对于根节点，它的前驱结点是左子树的最后一个结点（即左子树的最右结点）
记当前的结点为cur 若cur有左子树，则pre=cur的左子树的最右结点 若pre的右孩子为空，则将它的右孩子指向cur，并进入cur的左孩子 若pre的右孩子是cur(上次访问时，上一种情况下设置的)，则访问cur，删去pre的指向(还原原来的树结构)，并进入cur的右孩子 若cur没有左子树，那么访问cur本身，然后进入cur的右孩子 class Solution { public: void morris(TreeNode* root) { TreeNode *pre = nullptr; while (root != nullptr) { if (root->left != nullptr) {// 当前结点root的左子树不为空 pre = root->left; while (pre->right != nullptr && pre->right != root) { pre=pre->right; }//找到左子树的最右结点，或者回到了root本身 if (pre->right == nullptr) {//右孩子为空 pre->right = root;//将它的右孩子指向cur(此处改变了树结构) root = root->left;//进入root的左孩子 }else { //此处访问root pre->right = nullptr;//恢复原来的树结构 root = root->right;//进入root的右孩子 } }else {//root没有左孩子 //此处访问root root = root->right;//进入root的右孩子 } } } };先序遍历的情况类似：
void morris(TreeNode *root){ TreeNode *pre = nullptr; while (root != nullptr){ if (root->left != nullptr){ pre=root->left; while(pre->right != nullptr && pre->right != root){ pre = pre->right; } if (pre->right == nullptr){ pre->right = root; //此处访问root root = root->left; }else{ p2->right = nullptr; root = root->right; } }else{ //此处访问root root = root->right; } } }后序遍历情况比较复杂：
当前结点cur的左子树不为空 左子树的最右孩子为空，则最右孩子pre的右结点指向当前结点cur，进入右子树 左子树的最右孩子指向当前结点，则删除这个指向，并“逆序访问左子树的所有右孩子”，进入右子树 解释：由于右孩子指向当前结点，说明这是第二次访问cur; 在两次访问之间，一定已经访问过cur的左孩子； 那么对于cur的左孩子，要么它的左孩子为空，要么已经“逆序访问过了左子树的所有右孩子”； 一层一层迭代下去，则对于左-右-根的顺序，“左”的部分一定已经访问完成了； 所以可以看成cur的左子树的每个结点都没有左孩子，所以逆序访问右孩子即可完成“右-根” 左子树为空，则进入右子树如图： 第二次访问结点2时，访问路径1； 第二次访问结点1时，访问路径2； 第二次访问结点3时，访问路径3； 程序的最后访问根节点代表的路径4，结束
代码：
void morris(TreeNode *root){ TreeNode* pre,cur; cur=root; while (cur != nullptr){ if (cur>left != nullptr){ pre=cur->left; while(pre->right != nullptr && pre->right !=cur){ pre = pre->right; } if (pre->right == nullptr){//第一次访问cur，指向空 pre->right = cur; cur = cur->left; }else{//第二次访问cur，指向cur pre->right = nullptr; //逆序访问cur左子树的右边界 cur=cur->right; } }else//cur没有左孩子的情况 cur = cur->right; } //逆序访问root的右边界（注意这里在循环外面了） }关于逆序访问，在保证空间复杂度为O(1)的情况下，需要先把右孩子们（可以看成链表了）转置，访问完成后再转置回来，这里不再给出代码了
