算法1：做一个容器，我们在遍历二叉树寻找节点的同时，把从根到节点的路径扔进去（两个节点就是两个容器）。由于根节点最后一个被扔进去，但我们接下来又需要第一个就能访问到它——后进先出，所以这个容器是一个栈。时间复杂度O(N)，空间复杂度O(N)。

static bool GetPositionByNode(BinNode root,BinNode node, ref Stack stack)
{
  if (root == null)
      return false;
  if (root == node)
   {
      stack.Push(root);
      return true;
   }
  if (GetPositionByNode(root.Left, node, ref stack) ||GetPositionByNode(root.Right, node, ref stack))
   {
      stack.Push(root);
      return true;
   }
  return false;
}

然后我们要同时弹出这两个容器的元素，直到它们不相等，那么之前那个相等的元素就是我们要求的父亲节点。

static BinNode FindParentNode(BinNode root,BinNode node1, BinNode node2)
{
  Stack stack1 = new Stack();
  GetPositionByNode(root, node1, ref stack1);
  Stack stack2 = new Stack();
  GetPositionByNode(root, node2, ref stack2);
  BinNode tempNode = null;
  while (stack1.Peek() == stack2.Peek())
   {
      tempNode = (BinNode)stack1.Pop();
      stack2.Pop();
   }
  return tempNode;
}

算法2：如果要求o(1)的空间复杂度，就是说，只能用一个变量来辅助我们。

我们选择一个64位的整数，然后从1开始，从左到右逐层为二叉树的每个元素赋值，root对应1，root.Left对应2，root.Right对应3，依次类推，而不管实际这个位置上是否有节点，我们发现两个规律：

////                               1

////                 2                          3

////          4            5            6            7

////   8            9            10

如果要找的是5和9位置上的节点。

我们发现，它们的二进制分别是101和1001，右移1001使之与101位数相同，于是1001变成了100（也就是9的父亲4）。

这时101和100（也就是4和5位于同样的深度），我们从左往右找，101和100具有2位相同，即10，这就是我们要找的4和5的父亲，也就是9和5的最近父亲。

由上面观察，得到算法：

1)将找到的两个节点对应的数字

static bool GetPositionByNode(BinNode root,BinNode node, ref int pos)
{
  if (root == null)
      return false;
  if (root == node)
      return true;
  int temp = pos;
  //这么写很别扭，但是能保证只要找到就不再进行下去
  pos = temp * 2;
  if (GetPositionByNode(root.Left, node, ref pos))
   {
       return true;
   }
  else
   {
      //找不到左边找右边
      pos = temp * 2 + 1;
      return GetPositionByNode(root.Right, node, ref pos);
   }
}

2)它们的二进制表示，从左向右逐一比较，直到一个结束或不再相同，则最大的相同子串，就是我们需要得到的最近父亲所对应的位置K。

static int FindParentPosition(int larger,int smaller)
{
  if (larger == smaller) return larger;
  int left = GetLen(larger) - GetLen(smaller);
  while (left > 0)
   {
      larger = larger >> 1;
      left--;
   }
  while (larger != smaller)
   {
      larger = larger >> 1;
      smaller = smaller >> 1;
   }
  return smaller;
}
static int GetLen(int num)
{
  int length = 0;
  while (num != 0)
   {
      num = num >> 1;
      length++;
   }
  return length;
}

3)第3次递归遍历，寻找K所对应的节点。

函数GetNodeByPosition的思想是，先算出k在第几层power，观察k的二进制表示，比如说12，即1100，从左向右数第一个位1不算，还剩下100，1表示向右走，0表示向左走，于是从root出发，1->3->6->12。

static BinNode GetNodeByPosition(BinNoderoot, int num)
{
  if (num == 1) return root;
  int pow = (int)Math.Floor(Math.Log(num, 2)); //1 return 0, 2-3 return 1,4-7 return 2
  //第一个位不算
  num -= 1 << pow;
  while (pow > 0)
   {
      if ((num & 1 << (pow - 1)) == 0)
          root = root.Left;
      else
          root = root.Right;
      pow--;
   }
  return root;
}

总结上面的3个步骤：

static BinNode FindParentNode(BinNode root,BinNode node1, BinNode node2)
{
  int pos1 = 1;
  GetPositionByNode(root, node1, ref pos1);
  int pos2 = 1;
  GetPositionByNode(root, node2, ref pos2);
  int parentposition = 0;
  if (pos1 >= pos2)
   {
      parentposition = FindParentPosition(pos1, pos2);
   }
  else //pos1<pos2
   {
      parentposition = FindParentPosition(pos2, pos1);
   }
  return GetNodeByPosition(root, parentposition);
}