题目：
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_6
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
思路：
二叉树两个节点的最近的父节点。二叉树遍历，从根节点遍历左节点和右节点，判断当前节点是否包含两个节点，如果是的话，马上停止遍历，第一次出现的2的时候，即为最近的父节点。如下图，如果目标是寻找3和5的LCA，首先进入6->2->4，那么在4节点先知道该节点包含2个节点，则停止遍历。算法复杂度：O（logN）
_6
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
代码：
/**
- 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)
{
m_pAncestor = NULL;
HasNodeCount(root, p, q);
return m_pAncestor;
}
//if it return 2, it's the common ancestor,-1 is find it
int HasNodeCount(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (root == NULL)
{
return 0;
}
int node_count = 0;
int left_count = 0;
int right_count = 0;
int cur_count = 0;
if (root->left != NULL)
{
left_count = HasNodeCount(root->left, p, q);
}
if (root->right != NULL)
{
right_count = HasNodeCount(root->right, p, q);
}
if (p != NULL && root->val == p->val)
{
cur_count++;
}
if (q != NULL && root->val == q->val)
{
cur_count++;
}
if (left_count == -1 || right_count == -1)
{
return -1;
}
node_count = left_count + right_count + cur_count;
if (node_count == 2)
{
m_pAncestor = root;
return -1;
}
return node_count;
}
private:
TreeNode* m_pAncestor;
};
总结：
1、理解Lowest Common Ancestor of a Binary (LCA)，即最近父节点。
2、使用迭代的算法，一定要找到其终结点。比如该终结点是 return -1；和return 0;
3、代码比较紊乱，不想整理了，等下次刷题时再优化吧。