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

1. Use recursion:

  1. //40 ms    23.5 MB
  3. /**
  4.  * Definition for a binary tree node.
  5.  * struct TreeNode {
  6.  *     int val;
  7.  *     TreeNode *left;
  8.  *     TreeNode *right;
  9.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  15.         if(!root) return NULL;
  17.         if(p->val > root->val && q->val > root->val)
  18.             return lowestCommonAncestor(root->right, p, q);
  19.         else if(p->val < root->val && q->val < root->val)
  20.             return lowestCommonAncestor(root->left, p, q);
  21.         else 
  22.             return root;
  23.     }
  24. };

2. Use iteration:

  1. //44 ms    23.3 MB
  3. /**
  4.  * Definition for a binary tree node.
  5.  * struct TreeNode {
  6.  *     int val;
  7.  *     TreeNode *left;
  8.  *     TreeNode *right;
  9.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  15.         if(!root) return NULL;
  17.         while(root){
  18.             if(p->val > root->val && q->val > root->val)
  19.                 root = root->right;
  20.             else if(p->val < root->val && q->val < root->val)
  21.                 root = root->left;
  22.             else 
  23.                 return root;
  24.         }
  26.         return NULL;
  27.     }
  28. };