Leetcode 236: lowest Common Ancestor 小结

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

 1.different tree structure:

    1.1 if the tree is binary search tree

    1.2 if the tree has parent pointer but not given the root

    1.3 if the tree has no parent pointer but given the root

    

 2. depending on the upcoming nodes (input)

     2.1 LCA(m1, m2,m3.....) all nodes are in the tree

     2.2 LCA(m1,m2,...........) nodes are not guaranteed in the tree.

下面对这个题目不同的情况进行分析：
1.1  if the tree is a binary search tree
如果看到binary search tree的话，就要想到利用binary search tree的性质，然后自己随便举一个例子应该可以发现规律。
                5               比如左边的binary search tree里面，2和8的lca就是5了，2,4 的lca
             /    \             就是3了， 2,3 的LCA 是3
           3      8            可以发现规律就是： 如果m1, m2的值都比current node的值小 那么
          /  \                  LCA在左子树，如果m1,m2的值都比current node的值大，那么LCA
       2      4                在右子树，如果m1, m2在current node两边，那么current node是
LCA，还有一种很重要的情况，如果current node与m1, m2其中一个值相等，那么current node也是LCA，最后两种情况是可以合并的，但是都需要考虑到， LCA题目里面最容易忽略的一种情况就是m1, m2其中一个是另一个的lca。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //sanity check
        if (root == NULL) return NULL;
        while (root) {
            //case 1
            if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else if (root->val > p->val && root->val > q->val) {
                //case2
                root =root->left;
            } else break; //case 3, 4
        }
        return root;
    }
};

time complexity: O(h) , h 是树的高度，对于unbalanced binary search tree: O(n)
对于balanced binary search tree来说，是O（logn)/

1.2  if the tree has parent pointer but not given the root

In this case, the binary tree can be regarded as a linklist, the parent node is like the next pointer, one link list is starting from m1 and end at NULL, the other linklist is starting from m2 and end at NULL, finding the LCA of the two linklist is finding the intersect point of the two linklist. 
step1: get the length of the two linklist, 
step2: to avoid the duplicate code, we can keep one node as the longer head, the other node as the shorter head.
step3: move the head of the linklist with  a larger length to catch up with the linklist with a shorter length
step4: move the two heads together and get the intersection pointer when they meet each other

一般的处理情况里面包含了如果two nodes are not guaranteed in the tree, one of the nodes are NULL, then it will jump out from the while loop and return NULL;

class Solution {
 private:
  int getHeight(TreeNodeP* node) {
    if (node == NULL) return 0;
    int len = 0;
    while (node) {
      len++;
      node = node->parent;
    }
    return len;
  }
 public:
  TreeNodeP* solve(TreeNodeP* one, TreeNodeP* two) {
    //sanity check
    if (one == NULL && two == NULL) return NULL;
    int len1 = getHeight(one);
    int len2 = getHeight(two);
    if (len2 < len1) {
      return solve(two, one);
    }
    int diff = len2 - len1;
    while (diff) {
      two = two->parent;
      diff--;
    }
    while ( one != two) {
      one = one->parent;
      two = two->parent;
    }
    return one;
  }
};

time complexity: O(h)

1.3  if the tree has no parent pointer but given the root

 前面两种情况都是比较简单的情况，1.3这种情况开始才是basic的解决一般lca问题。
LCA属于与binary tree相关的问题，一般binary tree的问题，除了要求是top-down的题目，我们都可以按照down- top的递归解法，down - top的基本思路： 
step1: what current node wants from its children, from left and from right --> successor
step2: what current node do in current level
step3: what current node return to its parent --> reporting to its predescesor.  
可以随便画一个binary tree来看具体怎么去做：‘

                         5                       step1: 对于任意一个node， 看做是current node, 它需要向它的左子
                       /   \                                 树要左子树要m1或者 m2在左子树的LCA 也需要向它的右子树
                    8      4                               要m1或者 m2在右子树的LCA
                  /   \    /   \                  step2: 在当前做什么？ 有几种情况， 如果m1, m2在 左右子树的LCA
               6      7 3    1                           都不为NULL，说明当前的node就是m1, m2的LCA,此时m1,
              /                                              m2分布在node的两边； 如果m1, m2在左右子树的LCA有一个
            2                                               为NULL，说明m1, m2在node的某一边，那个不为NULL的那边返回给parent就可以；也有可能两边是NULL，说明此时的current node与m1, m2的LCA无关，直接返回给parent NULL就可以了。
step3: 其实在step2里面分析完了。
bottom-up的recursion其实是一个post - order traversal的过程， 需要把整棵树都遍历一遍才可能找到正确的LCA。

//assume two nodes are in the tree and no parent

//bottom- up recursion

TreeNode* LCA(TreeNode* root, TreeNode* a, TreeNode* b) {

   //sanity check

   If (root == NULL) {

      return NULL;

   } 

   //case 1,case 2

   If (root == a || root == b) {

      return root;

   } 

  

   TreeNode* left = LCA(root->left, a, b);

   TreeNode* right = LCA(root->right, a, b);

   //case2

   If (left != NULL && right !=NULL) {

      return root;

   }

   If (left == NULL && right == NULL) {

      return NULL;

   }

    //caes 3, case 4, case5

   Return (left) ? left : right;

}

time complexity: O(n)： 
use one sentence to explain why the time complexity is O(n):
because each node in the tree is visited once.


从find 2 nodes LCA -> find k nodes LCA , 这种是一个很重要的算法思想， 2 --> k， 见过的类似推广有：
1. merge two sorted linklist/array    --> merge k sorted linklist/array
2. sort two color-> sort 3 color --> sort k color
3. 2sum/3sum -> k sum
从2 --> 推广到n的一般思路有：
Common idea: 
1. basic solution: iteratively / recursively apply 2 way solution to k way solution (trival but slow) -> but definitely works.  如果在面试的时候被问到而没有准备过的这种题目，直接上basic solution, 至少不会出错。
2.  divide and conquer： recursion
或者 直接modify the 2-way solution: 
这种方法比较不容易想到， 而且在面试的时候即使想到可能还不能确定是不是正确的方案，所以对于一些之前没有做过的这类题目，先上common idea, 如果面试官硬要直接Modify的话，再说说思路。
1. 2 array comparison to priority queues.
    if only 2 array, we can use comparison, but k array, we need to use priority queue to find the minimal/ maximum element in the k array.( this method can be applied to merge k sorted array. )
2.  bool flag to counting
when solving 2 way , we use bool flag to notify whether we find or not, when solving k way, we can use a counter to keep track of how many we have found, how many subproblems we have solved. 

 2. depending on the upcoming nodes (input)

     2.1 LCA(m1, m2,m3.....) all nodes are in the tree 

    method1 :  we can iteratively use 2 way solution: time complexity is O(n * k)

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;
  }
};

method 2: we can modify the 2 way solution to make it appliable to k way solution

counting : from bottom-up , we find the LCA, and count the num of nodes we found, if we find all the nodes, we find the lowest common ancester, after that we shouldn't change that value.

if the input can be changed to unordered_set, we can make the time complexity to be O(n) 

 

class Solution {
 private:
  int helper(TreeNode* root, vector<TreeNode*> nodes, TreeNode* &rst) {
    //base cae
    if (root == NULL) return 0;
    //what current node wants from its children
    int left = helper(root->left, nodes, rst);
    int right = helper(root->right, nodes, rst);
    //what current node do in current level
    int num = left + right;
    if (find(nodes.begin(), nodes.end(), root) != nodes.end()) {
       num = num + 1;
    }
    //if all the nodes are find, then we find the LCA
    //and rst  == NULL can make sure that the CA is the lowest,
    //when bottom-up, when first find CA, that's the lowest, never change it later
    if (num == nodes.size() && (rst == NULL)) {
      rst = root;
    }
    //return what to its parent
    return num;
  }
 public:
  TreeNode* solve(TreeNode* root, vector<TreeNode*> nodes) {
    TreeNode* rst = NULL;
    int count = 0;
    count  = helper(root, nodes, rst);
    return rst;
  }
};

method3 : also modify the 2-way solution,

from bottom-up, if the current node are one of the nodes, report this node to its parent. 

 ???????????????分析未完！！！！！！！！！！！！！！！

class Solution {
 public:
  TreeNode* solve(TreeNode* root, vector<TreeNode*> nodes) {
    //base case
    if (root == NULL) return NULL;
    TreeNode* left = solve(root->left, nodes);
    TreeNode* right = solve(root->right, nodes);
    if (find(nodes.begin(), nodes.end(), root) != nodes.end()) {
      return root;
    }
    if (left && right) return root;
    return (left) ? left : right;
  }
};

     2.2 LCA(m1,m2,...........) nodes are not guaranteed in the tree.
the counting method still works, only need to check if the num  ==   nodes.size()



if the incoming nodes are only two nodes: m1, m2

we can use a bool vector to keep track of whether the two nodes are all in the tree, but we have to change the recursion order from preorder to postorder, because if we still do in preorder way, then we can't check the case when one is the ascendent  of two, when we check one is the root , then we return, but we didn't check two. But if we do this in postorder way, we can check from bottom to top, in this case, we can check all these two nodes before we return. 








class Solution {
 private:
  TreeNode* helper(TreeNode* root, TreeNode* one, TreeNode* two, vector<bool> &flag) {
    //base case
    if (root == NULL) return NULL;
    TreeNode* left = helper(root->left, one, two, flag);
    TreeNode* right = helper(root->right, one, two, flag);
    if (root == one) {
      flag[0] = true;
      return root;
    }
    if (root == two) {
      flag[1] = true;
      return root;
    }
    if (left && right) {
      return root;
    }
    return (left) ? left : right;
  }
 public:
  TreeNode* solve(TreeNode* root, TreeNode* one, TreeNode* two) {
    vector<bool> flag(2, false);
    TreeNode* rst = helper(root, one, two, flag);
    if (flag[0] && flag[1]) return rst;
    return NULL;
  }
};
time complexity: post order traversal ==> O(n), each node in the tree is visited once.