LeetCode 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )

题目描述 : 

解题思路 : 使用递归查找 , 如果有一个节点与根节点匹配 , 那么直接返回根节点 , 否则依次在左子树和右子树中查找 ,并且用left和right分别记录左子树的返回值和右子树的返回值 , 如果节点都存在左子树中 , 那么right就一定为NULL , 只需要返回 left , 如果节点都存在右子树中那么直接返回 right , 如果left和right都为空 返回NULL ;

代码如下 :

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    //如果找到p或q中任意一个直接返回
    if(root==NULL||root->val==p->val||root->val==q->val)
        return root;
    struct TreeNode* left=lowestCommonAncestor(root->left,p,q);
    struct TreeNode* right=lowestCommonAncestor(root->right,p,q);
    //左右节点都不为空返回根节点
    if(left&&right)
        return root;
    //左节点为空,返回右节点
    else if(left==NULL)
        return right;
    //右节点为空,返回左节点
    else if(right==NULL)
        return left;
    else
        return NULL;
}