對情況進行分類:
(1)如果root為空,則傳回NULL;
(2)如果p和q其中之一為root,則這個節點就是最近公共祖先,傳回root;
其他情況下,p和q有可能都在root的左子樹、都在root的右子樹、或者左右子樹各一個; (3)遞歸計算lowestCommonAncestor(root -> left, p, q)和lowestCommonAncestor(root -> right, p, q),在root的 左右子樹中分别尋找p,q的公共祖先,如果找不到,傳回的結果是NULL。 如果左子樹找不到,則傳回右子樹中的查找結果,右子樹找不到就傳回左子樹的查找結果,都找不到,就是p和q左右各一個,傳回root。
/**
* 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(root == NULL || p == root || q == root) {
return root;
}
TreeNode* L = lowestCommonAncestor(root -> left, p, q);
TreeNode* R = lowestCommonAncestor(root -> right, p, q);
if(L == NULL) {
return R;
}
if(R == NULL) {
return L;
}
return root;
}
};