Leetcode235/236： lowest common ancesterI II III IV / lowest common ancester in binary search tree

Lowest common ancester I ：
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

         _____3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

 For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

树的recursion 经典的3段式， 其实找lowest common ancestor的问题就是以current为root在左右子树找p 和q，current node返回给parent找到的p,q的common ancestor。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //base case
        if (root == NULL) return NULL;
        //find the node
        if (root == p ) return p;
        if (root == q) return q;
        //what current node want from children
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        //what current node do in current level
        //what current node return to parent
        if (left && right) {
            return root;
        }
        if (!left) return right;
        if (!right) return left;
    }
};

time complexity: O (n)

Lowest Common Ancestor II

Data Structure

Given two nodes in a binary tree (with parent pointer available), find their lowest common ancestor.
Assumptions

• There is parent pointer for the nodes in the binary tree
• The given two nodes are not guaranteed to be in the binary tree

Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2 and 14 is 5
The lowest common ancestor of 2 and 9 is 9
The lowest common ancestor of 2 and 8 is null (8 is not in the tree)

 //class TreeNodeP {
// public:
//  int value;
//  TreeNodeP* left;
//  TreeNodeP* right;
//  TreeNodeP* parent;
//  TreeNodeP(int v, TreeNodeP* p)
//      : value(v), left(NULL), right(NULL), parent(p) {}
//};
已知parent node找common ancester，就像是两条链表，找两条链表的intersection point.这个题目里面就是按照parent指针往前找。都不在链表里面的情况是没有相交点。

class Solution {
 public:
  TreeNodeP* solve(TreeNodeP* one, TreeNodeP* two) {
    //sanity cehck
    if (one == NULL && two == NULL) return NULL;
    //step1: find two list length
    int len1 = 0;
    int len2 = 0;
    TreeNodeP* p1 = one;
    TreeNodeP* p2 = two;
    while (p1) {
      len1++;
      p1 = p1->parent;
    }
    while (p2) {
      len2++;
      p2 = p2->parent;
    }
    //step2: move one forward n
    if (len1 > len2) {
      for (int i = 0; i < len1 - len2;i++) {
        one = one->parent;
      }
    } else if (len1 < len2) {
      for (int i = 0; i < len2 - len1; i++) {
        two = two->parent;
      }
    }
    //step3: start from the same position and move forward
    while (one != NULL && two != NULL && one != two) {
      one = one->parent;
      two = two->parent;
    }
    if (one == NULL || two == NULL) return NULL;
    return one;
  }
};
time complexity: O(h)

Lowest Common Ancestor III

Given two nodes in a binary tree, find their lowest common ancestor (the given two nodes are not guaranteed to be in the binary tree).
Return null If any of the nodes is not in the tree.
Assumptions

• There is no parent pointer for the nodes in the binary tree
• The given two nodes are not guaranteed to be in the binary tree

Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2 and 14 is 5
The lowest common ancestor of 2 and 9 is 9
The lowest common ancestor of 2 and 8 is null (8 is not in the tree)

这题选的做法是加了一个find函数， 看这两个节点是不是在树里面，如果在就返回LCA
如果不在，就返回NULL。 

class Solution {
private:
  bool find(TreeNode* root, TreeNode* p) {
    //base caser
    if (p == NULL) return false;
    if (root == NULL) return false;
    if (root == p) return true;
    if (find(root->left, p)) return true;
    if (find(root->right, p)) return true;
    return false;
  }
  TreeNode* LCA(TreeNode* root, TreeNode* one, TreeNode* two) {
    if (root == NULL) return NULL;
    if (root == one || root == two) return root;
    TreeNode* left = LCA(root->left, one, two);
    TreeNode* right = LCA(root->right, one, two);
    if (left && right) return root;
    return left ? left : right;
  }
 public:
  TreeNode* solve(TreeNode* root, TreeNode* one, TreeNode* two) {
    //base case
    if (root == NULL) return NULL;
    if (find(root, one) && find(root, two)) {
      return LCA(root, one, two);
    } else {
      return NULL;
    }
  }
};
Lowest Common Ancestor IV

Given K nodes in a binary tree, find their lowest common ancestor.
Assumptions

• K >= 2
• There is no parent pointer for the nodes in the binary tree
• The given two nodes are guaranteed to be in the binary tree

Examples
        5
      /   \
     9     12
   /  \      \
  2    3      14
The lowest common ancestor of 2, 3, 14 is 5
The lowest common ancestor of 2, 3, 9 is 9

class Solution {
 private:
  TreeNode* LCA(TreeNode* root, TreeNode* one, TreeNode* two) {
    //base case
    if (root  == NULL) return NULL;
    if (root == one || root == two) return root;
    TreeNode* left = LCA(root->left, one, two);
    TreeNode* right = LCA(root->right, one, two);
    if (left && right) return root;
    return left ? left : right;
  }
 public:
  TreeNode* solve(TreeNode* root, vector<TreeNode*> nodes) {
    //sanity check
    if (root == NULL) return NULL;
    TreeNode* lca = nodes[0];
    for (int i = 1; i < nodes.size(); i++) {
      lca = LCA(root, lca, nodes[i]);
    }
    return lca;
  }
};

lowest common ancester in binary search tree
recursion VERSION: 
binary search tree, 可以分为p, q在root两边， p, q, 在root 左边， p,q在root右边。
 class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //base case
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;
        if ((root->val < q->val && root->val > p->val) || (root->val > q->val && root->val < p->val)) {
            return root;
        }
        if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }else {
            return lowestCommonAncestor(root->left, p, q);
        }
    }
};
 iterative version:
iterative 解这题好像更好一些。
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //sanity check
        if (root == NULL) return NULL;
        while (root) {
            if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else if (root->val > p->val && root->val > q->val) {
                root =root->left;
            } else break;
        }
        return root;
    }
};