题解 | #在二叉树中找到两个节点的最近公共祖先#

递归：

1. 如果当前root是o1或o2，则当前root为要找的公共祖先；
2. 否则：
   1. 如果o1和o2都在左（右）子树，则递归去子树中寻找；
   2. 如果o1和o2分散在左右子树中，则当前root为要找的公共祖先

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return dfs(root,o1,o2)->val;
    }
    TreeNode* dfs(TreeNode* root, int o1,int o2){
        // 最近的节点
        if(root == nullptr || root-> val == o1 || root->val == o2) return root;
        
        // 如果左子树o1和o2都没有，则可能在右子树
                // 或者左右子树都没有,则root子树也没有
        TreeNode* left = dfs(root->left,o1,o2);
        if(left == nullptr) return dfs(root->right,o1,o2);
        
        // 如果左子树有o1或者o2，看右子树有没有
        TreeNode* right = dfs(root->right,o1,o2);
        if(right == nullptr) return left; // 如果右子树没有，则左子树肯定同时包含o1和o2
        
        // 如果左右子树都有，则肯定是一边一个
        return root;
    }
};

非递归：

注意：非递归的后序遍历中，栈中保存的是根节点到当前遍历节点的路径

因此可以用两个栈分别保存o1和o2的路径，再进行比较

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<TreeNode*> v1, v2;
        v1 = zuxian(root, o1);
        v2 = zuxian(root, o2);
        int i = 0;
        for(; i < v1.size() && i < v2.size(); i ++){
            if(v1[i]->val != v2[i]->val)
                return v1[i - 1]->val;
        }
        return v1[i - 1]->val;
    }
    
    vector<TreeNode*> zuxian(TreeNode* root, int o){
        vector<TreeNode*> v;
        TreeNode* temp = root, * pre = NULL;
        while(temp || !v.empty()){
            while(temp){
                v.push_back(temp);
                temp = temp->left;
            }
            temp = v.back();
            if(temp->right && temp->right != pre)
                temp = temp->right;
            else{
                if(temp->val == o)
                    return v;
                v.pop_back();
                pre = temp;
                temp = NULL;
            }
        }
        return v;
    }
};