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

因为二叉搜索树为有序树，所以可以判断当前结点和p,q的值来决定递归的方向，

递归法

当当前结点的值在[p,q]之间的时候，该节点就是最近公共祖先

  1. class Solution {
  2. public:
  3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  4.         if(root==NULL)return root;
  5.         if(root->val > p->val && root->val > q->val)
  6.         {
  7.             TreeNode* left = lowestCommonAncestor(root->left,p,q);
  8.             if(left)return left;
  9.         }
  10.         if(root->val < p->val && root->val < q->val)
  11.         {
  12.             TreeNode* right = lowestCommonAncestor(root->right,p,q);
  13.             if(right)return right;
  14.         }
  15.         return root;
  16.     }
  17. };

精简

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

迭代法

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