lintcode 88. Lowest Common Ancestor of a Binary Tree

image.png

image.png

https://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-i/

image.png

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
        // write your code here
        if(root == NULL) return NULL;
        if(root == A || root == B) return root;
        int mat = countMatches(root->left, A, B);
        if(mat == 1) return root;
        if(mat == 2){
            return lowestCommonAncestor(root->left, A, B);
        }
        if(mat == 0){
            return lowestCommonAncestor(root->right, A, B);
        }
    }
private:
    int countMatches(TreeNode * root, TreeNode * p, TreeNode * q){
        if(root == NULL) return 0;
        int matches = countMatches(root->left, p, q) + countMatches(root->right, p , q);
        if(root == p || root == q){
            matches += 1;
        }
        return matches;
        
    }
};