LeetCode235.二叉搜索树的最近公共祖先

题目

 1 class Solution {
 2 public:
 3     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 4         if((p->val - root->val) * (q->val - root->val)<0) return root;
 5         //if(root == p ) return p;
 6         //if(root == q) return q;
 7         if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left,p,q);
 8         if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right,p,q);
 9         return root;
10     }
11 };

官方答案，学习

 1 class Solution {
 2 public:
 3     vector<TreeNode*> getPath(TreeNode* root,TreeNode* target){
 4         vector<TreeNode*>path;
 5         TreeNode* node = root;
 6         while(node!=target){
 7             path.push_back(node);
 8             if(target->val > node->val) node = node->right;
 9             else node = node->left;
10         }
11         path.push_back(node);
12         return path;
13     }
14     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
15         vector<TreeNode*>path_p = getPath(root,p);
16         vector<TreeNode*>path_q = getPath(root,q);
17         TreeNode* ancestor;
18         for(int i = 0;i < path_p.size() && i < path_q.size();i++){
19             if(path_p[i] == path_q[i]) ancestor = path_p[i];
20             else break;
21         }
22         return ancestor;
23 
24     }
25 };