#includeusing namespace std;struct TreeNode{ int val; TreeNode* right; TreeNode* left; TreeNode(int _val):val(_val),right(nullptr),left(nullptr){}};void Morris(TreeNode* root){ if(root == nullptr) return; TreeNode* cur=root; TreeNode* mostRight=nullptr; //当cur为空停止，即上图中的情况3 while(cur != nullptr){ mostRight=cur->left; //如果mostRight!=nullptr，进入情况2 if(mostRight != nullptr){ while(mostRight->right && mostRight != cur) mostRight=mostRight->right; //当mostRight == nullptr，即情况2.a if(mostRight->right == nullptr){ mostRight->right=cur; cur=cur->left; continue; } else{ //当mostRight == cur，即情况2.b mostRight->right=nullptr; /*cur=cur->left; continue;*/ } } //mostright为空进入情况1 cur=cur->left; }}
Morris前序遍历
有左子树就会回到cur节点两次，没有就来一次
void MorrisPre(TreeNode* root) { if (root == nullptr) return; TreeNode* cur = root; TreeNode* mostRight = nullptr; while (cur != nullptr) { mostRight = cur->left; if (mostRight != nullptr) { while (mostRight->right && mostRight->right != cur) { mostRight = mostRight->right; } if (mostRight->right == nullptr) { //第一次到达左子树的最右子树 printf("%d ", cur->val); mostRight->right = cur; cur = cur->left; continue; } else { //第二次到达左子树的最右子树 mostRight->right == cur; mostRight->right = nullptr; /*cur = cur->right; continue;*/ } } else { //当前cur只能来一次 printf("%d ", cur->val); } cur = cur->right; }}
Morris中序遍历
void MorrisIn(TreeNode* root) { if (root == nullptr) return; TreeNode* cur = root; TreeNode* mostRight = nullptr; while (cur != nullptr) { mostRight = cur->left; if (mostRight != nullptr) { while (mostRight->right && mostRight->right != cur) { mostRight = mostRight->right; } if (mostRight->right == nullptr) { //第一次到达左子树的最右子树 mostRight->right = cur; cur = cur->left; continue; } else { //第二次到达左子树的最右子树 mostRight->right == cur; mostRight->right = nullptr; /*cur = cur->right; continue;*/ } } //往右移动的时候打印 printf("%d ", cur->val); cur = cur->right; }}
Morris后序遍历
//右孩子指向上一个节点TreeNode* ReverseNode(TreeNode* node) { TreeNode* pre = nullptr; TreeNode* next = nullptr; while (node) { next = node->right; node->right = pre; pre = node; node = next; } return pre;}//逆序打印左孩子的右边界void PrintNode(TreeNode* node) { TreeNode* tail = ReverseNode(node); TreeNode* cur = tail; while (cur) { printf("%d ", cur->val); cur = cur->right; } ReverseNode(tail); //还原}void MorrisPos(TreeNode* root) { if (root == nullptr) return; TreeNode* cur = root; TreeNode* mostRight = nullptr; while (cur != nullptr) { mostRight = cur->left; if (mostRight != nullptr) { while (mostRight->right && mostRight->right != cur) { mostRight = mostRight->right; } if (mostRight->right == nullptr) { //第一次到达左子树的最右子树 mostRight->right = cur; cur = cur->left; continue; } else { //第二次到达左子树的最右子树 mostRight->right == cur; mostRight->right = nullptr; //逆序打印左子树的右边界 PrintNode(cur->left); } } cur = cur->right; } PrintNode(root);}