双栈保存路径法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    void recrusion(TreeNode* root, int p, int q, stack<int>& sp, stack<int>& sq)
    {
        if (!root)
        {
            return;
        }
        if (sp.empty() || sp.top() != p)
        {
            sp.push(root->val);
        }
        if (sq.empty() || sq.top() != q)
        {
            sq.push(root->val);
        }

        recrusion(root->left, p, q, sp, sq);
        recrusion(root->right, p, q, sp, sq);
        if (sp.top() != p) {
            sp.pop();
        }
        if (sq.top() != q)
        {
            sq.pop();
        }
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        //保存路径
        stack<int> sp;
        stack<int> sq;
        recrusion(root, p, q, sp, sq);
        while (sp.size() > sq.size())
        {
            sp.pop();
        }
        while (sp.size() < sq.size())
        {
            sq.pop();
        }
        while (sp.top() != sq.top())
        {
            sp.pop();
            sq.pop();
        }
        return sp.top();
    }
};

递归法

class Solution {
  public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        if (root == NULL)
            return -1;
        if (root->val == o1 || root->val == o2)
            return root->val;
        int left = lowestCommonAncestor(root->left, o1, o2);
        int right = lowestCommonAncestor(root->right, o1, o2);
        if (left == -1)
            return right;
        if (right == -1)
            return left;
        return root->val;
    }
};