题解 |符合空间复杂度O(1)的二叉树最近公共祖先解法（Morris遍历）

题目要求空间复杂度为O(1)，使用递归和堆缓存的方式遍历均不符合要求，考虑使用Morris遍历(Morris遍历过程不在赘述)。 同样，使用记录公共路径方法均会超过空间复杂度要求，下面简述种算法，供参考。

【场景分析】

1. 前序遍历，找到第一个目标节点 T1；
2. 第二个目标节点 T2有两种情况：1）在T1的左、右子树中；2）根节点到T1的路径中，其中一个路径节点的右子树中。
3. 遍历T1的左右子树，发现T2,即返回T1。
4. 遍历完T1左右子树后，沿T1的路径，逐个回溯T1的路径节点
5. 如果T1位于父节点的右子树，则继续回溯。
6. 如果T1位于路径节点的左子树，遍历路径节点的右子树，发现T2，即返回当前路径节点；未发现继续回溯。

【算法过程】

需要记录的值，当前检测的路径节点res，找到的节点计数count，当前路径节点是否遍历完成的标志changeRes。

1. 前序遍历，找到T1，另res = T1，计数count加1。
2. 发现T1后，检查后续遍历过程，若后续遍历到res，则表示res右子树遍历完，changeRes置为true；
3. 发现T1后，检查中序遍历过程，若changeRes为true，则回溯res，到当前节点的上级节点（中序遍历过程的下个节点）。
4. 继续遍历res的右子树，重复上述过程，直到发现T2或者搜索结束。

【代码】

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    TreeNode* Reverse(TreeNode* node)
    {
        TreeNode* p1 = node;
        TreeNode* p2 = p1->right;
        p1->right = nullptr;
        TreeNode* p3 = nullptr;
        while(p2)
        {
            p3 = p2->right;
            p2->right = p1;
            p1 = p2;
            p2 = p3;
        }
        return p1;
    }
    bool Trans(TreeNode* node, TreeNode* f)
    {
        bool res = false;
        TreeNode* rev = Reverse(node);
        TreeNode* p = rev;
        while(p)
        {
            if(p == f)
                res = true;
            p = p->right;
        }
        Reverse(rev);
        return res;
    }
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        int count = 0;
        TreeNode* res = nullptr;
        bool changeRes = false;
        while(cur)
        {
            pre = cur->left;
            if(pre)
            {
                while(pre->right && pre->right != cur)
                {
                    pre = pre->right;
                }
                if(pre->right)
                {
                    pre->right = nullptr;
                    if(count == 1)
                    {
                        changeRes = Trans(cur->left, res);
                        if(changeRes)
                        {
                            changeRes = false;
                            res = cur;
                        }
                    }
                    cur = cur->right;
                }
                else
                {
                    if(cur->val == o1 || cur->val == o2)
                    {
                        count++;
                        if(count == 1)
                        {
                            res = cur;
                        }
                        else if(count == 2)
                        {
                            return res->val;
                        }
                    }
                    pre->right = cur;
                    cur = cur->left;
                }
            }
            else
            {
                if(cur->val == o1 || cur->val == o2)
                {
                    count++;
                    if(count == 1)
                    {
                        res = cur;
                    }
                    else if(count == 2)
                    {
                        return res->val;
                    }
                }
                
                if(count == 1 && changeRes)
                {
                    changeRes = false;
                    res = cur;
                }
                cur = cur->right;
            }
        }
        return res ? res->val : -1;
    }
};