题意:在一颗普通的二叉树里找到两个节点的最近公共祖先。
题解:递归,如果当前节点等于p或者q,那返回当前节点了。 然后递归左子树,和右子树。 如果左子树和右子树返回的都不是NULL,说明当前节点是公共祖先。 否则返回两个子树有值的那一个。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(p->val==root->val||q->val==root->val)
return root;
TreeNode* term=NULL;
TreeNode* term2=NULL;
if(root->left!=NULL)
term = lowestCommonAncestor(root->left,p,q);
if(root->right!=NULL)
term2 = lowestCommonAncestor(root->right,p,q);
if(term!=NULL&&term2!=NULL)
return root;
if(term==NULL)
return term2;
if(term2==NULL)
return term;
return root;
}
};