LeetCode算法解题集：Lowest Common Ancestor of a Binary Search Tree

题目：
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、代码比较紊乱，不想整理了，等下次刷题时再优化吧。