1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
public:
    bool isFind;
    vector<TreeNode *> pV, qV;
    void FindK(TreeNode *node, TreeNode* k, vector<TreeNode *> &kV)
    {
        kV.push_back(node);
        if (isFind || node == k)
        {
            isFind = true;
            return;
        }
        if (NULL != node->left)
        {
            FindK(node->left, k, kV);
            if (isFind)
            {
                return;
            }
            kV.pop_back();
        }
        if (NULL != node->right)
        {
            FindK(node->right, k, kV);
            if (isFind)
            {
                return;
            }
            kV.pop_back();
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (NULL == root)
        {
            return root;
        }
        pV.clear();
        qV.clear();
        isFind = false;
        FindK(root, p, pV);
        isFind = false;
        FindK(root, q, qV);
        int i = 0;
        int minSize = pV.size() > qV.size() ? qV.size() : qV.size();
        for (i = 0;i < minSize; i++)
        {
            if (pV[i] != qV[i])
            {
                break;
            }
        }
        return pV[i - 1];
    }
};