注意事项

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param root: The root of the binary search tree.
17      * @param A and B: two nodes in a Binary.
18      * @return: Return the least common ancestor(LCA) of the two nodes.
19      */
20     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
21         // write your code here
22         TreeNode * ancestor = NULL;
23         if(root==NULL || A==NULL || B==NULL)
24             return ancestor;
25 
26         vector<TreeNode *> pathA, pathB;
27         searchTree(root, A, pathA);
28         searchTree(root, B, pathB);
29 
30         int sizeA=pathA.size(), sizeB=pathB.size();
31         int size = sizeA>sizeB ? sizeB : sizeA, i=0;
32         bool find = false;
33 
34         for(i=0; i<size; i++)
35         {
36             if(pathA[i] != pathB[i])
37             {
38                 find = true;
39                 return ancestor;
40             }
41             else
42                 ancestor = pathA[i];
43         }
44         if(find == false)
45             ancestor = pathA[size-1];
46         return ancestor;
47     }
48 
49     bool searchTree(TreeNode *root, TreeNode *node, vector<TreeNode *> &path) {
50         if(root==NULL || node==NULL) {  
51             return false;  
52         }
53 
54         path.push_back(root);
55 
56         //  找到了
57         if(root->val == node->val) {  
58             return true;  
59         }
60 
61         if(root->left != NULL) {  
62             if(searchTree(root->left, node, path)) {  
63                 return true;  
64             }  
65         }  
66         if(root->right != NULL) {  
67             if(searchTree(root->right, node, path)) {  
68                 return true;  
69             }  
70         }
71 
72         //回溯
73         path.pop_back(); 
74         return false;  
75     }
76 };