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

1.递归法，没什么大不了的

/**
 * 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 get<1>(lca(root,o1,o2));
    }
    pair<bool, int> lca(TreeNode* root, int o1, int o2) {
        if(!root) {
            return pair<bool, int>(false,-1);
        }
        if(root->val==o1 || root->val==o2) {
            return pair<bool, int>(true,root->val);
        }
        pair<bool, int> left = lca(root->left,o1,o2);
        pair<bool, int> right = lca(root->right,o1,o2);
        if(get<0>(left) && get<0>(right)) {
            return pair<bool, int>(true,root->val);
        }
        if(get<0>(left)) {
            return left;
        }
        if(get<0>(right)) {
            return right;
        }
        return pair<bool, int>(false,-1);
    }
};