【二叉树】二叉树的最近公共祖先

思路：递归解决（时间效率差）

如果结点p和q分别在左右子树，或者根结点为两个结点中一个，则说明当前根结点为最近公共祖先

创立一个递归函数判断两个结点是否在两个子树中：

递归结束条件：传入结点为NULL

前序遍历树，如果传入结点在子树中，返回1

int bothAreChildren(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if((isInLeft(root->left, p) && isInRight(root->right, q)) || (isInLeft(root->left, q) && isInRight(root->right, p)))
        return 1;
    return 0;
}

int isInLeft(struct TreeNode* root, struct TreeNode* key) {
    if(!root)
        return 0;
    if(root == key)
        return 1;
    return isInLeft(root->left, key) || isInRight(root->right, key);
}

int isInRight(struct TreeNode* root, struct TreeNode* key) {
    if(!root)
        return 0;
    if(root == key)
        return 1;
    return isInLeft(root->left, key) || isInRight(root->right, key);
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == p || root == q || bothAreChildren(root, p, q)) {
        return root;
    }
    if(isInLeft(root->left, p))
        return lowestCommonAncestor(root->left, p, q); 
    return lowestCommonAncestor(root->right, p, q);
}

解题思路：回溯解决

后序遍历自身就是回溯算法

递归结束条件：结点本身等于p、q其中之一或者NULL

1. 用left和right两个结点记录其左右孩子情况。如果在子树中找到了结点，会返回结点的地址，否则会返回NULL
2. 如果left和right其中一个结点有值，将它返回
3. 如果两个都有值，返回当前结点

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == p || root == q || !root)
        return root;
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if(left && right)
        return root;
    if(left && !right)
        return left;
    if(right && !left)
        return right;
    return NULL;
}