算法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);
}