看见一句话，感觉很好，记录一下：贵有恒，何须三更醒五更眠。最无益，莫过一日曝十日寒。
谈到中序遍历，常规的思路一个是递归，一个是迭代，其中迭代的思想需要显式的维护一个栈，以此来辅助遍历，但这连两种方法都不能达到O1的空间复杂度。刷题的时候看到一个巧妙的方法，利用二叉树中的闲散指针，每个节点访问两次，以时间换取空间的方法，O(2n)的时间也不会多出太久，达到了O1的空间占用。这种方法叫做Morris中序遍历。
原题为力扣中99. 恢复二叉搜索树，是一道难度不高的题，但贵在一题多解，这个方法很值得学习。
算法步骤如下：
- 如果 x 无左孩子，则访问 x 的右孩子，即 x=x.right。
- 如果 x 有左孩子，则找到x左子树上最右的节点（即左子树中序遍历的最后一个节点，x在中序遍历中的前驱节点），我们记为predecessor。根据predecessor 的右孩子是否为空，进行如下操作。
- 如果predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 x=x.left
- 如果predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将predecessor 的右孩子置空，然后访问x的右孩子，即x=x.right。
- 重复上述操作，直至访问完整棵树。
其实整个过程我们就多做一步：将当前节点左子树中最右边的节点指向它，这样在左子树遍历完成后我们通过这个指向走回了 xx，且能再通过这个知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。
代码实现如下：
void recoverTree(TreeNode* root) { TreeNode* x=nullptr; TreeNode* y=nullptr; TreeNode* pre=nullptr; TreeNode* predecessor=nullptr; while(root){ if(root->left){ //有左子树，遍历找到前序节点，然后指向root节点。 predecessor=root->left; while(predecessor->right && predecessor->right!=root){ predecessor=predecessor->right; } if(predecessor->right){ //有后续，需断开 if(pre&& pre->val>root->val){ y=root; if(x==nullptr){ x=pre; } } predecessor->right=nullptr; pre=root; root=root->right; } else{ //不需要断开 predecessor->right=root; root=root->left; } } else{ //无左子树 if(pre&& pre->val>root->val){ y=root; if(x==nullptr){ x=pre; } } pre=root; root=root->right; } } swap(x->val,y->val); }