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

题目描述 : 

方法一：

代码如下（附有解析）：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* FindNode(struct TreeNode* rootNode, struct TreeNode* Node) {if(rootNode==NULL)return NULL;if(rootNode==Node)return rootNode;struct TreeNode* ret=FindNode(rootNode->left,Node);if(ret){return ret;}return FindNode(rootNode->right,Node);
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if(root==p||root==q){return root;}bool pLeft,pRight,qLeft,qRight;//如果在左子树找到了，则将pLeft赋真，pRight赋假if(FindNode(root->left,p)){pLeft=true;pRight=false;}//如果在右子树找到了，则将pLeft赋假，pRight赋真else{pLeft=false;pRight=true;}//如果在左子树找到了，则将qLeft赋真，qRight赋假if(FindNode(root->right,q)){qLeft=false;qRight=true;}//如果在右子树找到了，则将qLeft赋假，qRight赋真else{qLeft=true;qRight=false;}//若当前节点就为公共祖先，那么pq两个节点肯定一个在左子树，一个在右子树，if((pLeft&&qRight)||(pRight&&qLeft))return root;//如果pq都在左子树，则递归到左子树去找if(pLeft&&qLeft)return lowestCommonAncestor(root->left,p,q);//如果pq都在右子树，则递归到右子树去找elsereturn lowestCommonAncestor(root->right,p,q);
}

方法二：

解题思路 : 使用递归查找 , 如果有一个节点与根节点匹配 , 那么直接返回根节点 , 否则依次在左子树和右子树中查找 ,并且用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;elsereturn NULL;
}

方法三：使用栈

代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode*  DataType;typedef struct Stack
{DataType * _a;int _top;        //栈顶的位置int _capacity;   //栈的容量
}Stack;
typedef struct StackMin
{Stack s1;Stack s2;
}StackMin;
void StackInit(Stack *ps);
void StackDestroy(Stack *ps);
void StackPush(Stack *ps, DataType x);
void StackPop(Stack *ps);
DataType StackTop(Stack *ps);
int StackEmpty(Stack *ps);
int StackSize(Stack *ps);
void StackInit(Stack *ps)
{ps->_a = (DataType *)malloc(sizeof(DataType)* 3);	assert(ps->_a);    ps->_top = 0;ps->_capacity = 3;}
void StackDestroy(Stack *ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}
void StackPush(Stack *ps, DataType x)
{assert(ps);if (ps->_top >= ps->_capacity){ps->_a = (DataType*)realloc(ps->_a, sizeof(Stack)* (ps->_capacity*2));assert(ps->_a);ps->_capacity *= 2;}ps->_a[ps->_top] = x;ps->_top++;
}
void StackPop(Stack *ps)
{assert(ps->_top>0&&ps);ps->_top--;
}
DataType StackTop(Stack *ps)
{assert(ps);return ps->_a[ps->_top-1];
}
int StackEmpty(Stack *ps)
{assert(ps);return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack *ps)
{assert(ps);return ps->_top;
}
int GetPath(struct TreeNode* root,struct TreeNode* x,Stack *path){if(root==NULL)return 0;StackPush(path,root);if(root==x)return 1;if(GetPath(root->left,x,path)==1)return 1;if(GetPath(root->right,x,path)==1)return 1;StackPop(path);return 0;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if(root==p||root==q){return root;}Stack pStack,qStack;StackInit(&pStack);StackInit(&qStack);GetPath(root,p,&pStack);GetPath(root,q,&qStack);while(StackSize(&pStack)!=StackSize(&qStack)){StackSize(&pStack)>StackSize(&qStack)?StackPop(&pStack):StackPop(&qStack);}while(StackTop(&pStack)!=StackTop(&qStack)){StackPop(&pStack);StackPop(&qStack);}struct TreeNode* ret=StackTop(&pStack);return ret;StackDestroy(&pStack);StackDestroy(&qStack);
}