Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

由于是二叉排序树，所以可以先确定一个搜索函数，方便构造出一个数组用于存放搜寻路径

之后再搜索路径中查找到最后重复的节点即可。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 
11 
12 class Solution {
13 public:
14     void getPath(TreeNode * root,TreeNode * p,vector<TreeNode *> & path)
15     {
16         TreeNode * temp=root;
17         while(temp!=NULL)
18         {
19             path.push_back(temp);
20             if(p->val==temp->val)
21                 break;
22             else if(p->val>temp->val)
23                 temp=temp->right;
24             else
25                 temp=temp->left;
26         }
27     }
28     int min(int a,int b)
29     {
30         return a<b?a:b;
31     }
32     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
33             
34             vector<TreeNode *> path1;
35             vector<TreeNode *> path2;
36             getPath(root,p,path1);
37             getPath(root,q,path2);
38             int size1=path1.size();
39             int size2=path2.size();
40             int i=0;
41             TreeNode * res=root;
42             for(;i<size1&&i<size2;i++)
43             {
44                 if(path1.at(i)->val==path2.at(i)->val)
45                 {
46                     res=path1.at(i);
47                 }
48                 else
49                     break;
50             }
51             return res;
52                 
53     }
54 };