欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:39:04
...

题目描述 : 

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;
}