document.write('方法一：路径对比法
对于一棵二叉树的两个结点，如果知道了从根结点到这两个结点的路径，就可以很容易地找出它们最近的
公共父结点。因此，可以首先分别找出从根结点到这两个结点的路径(例如上图中从根结点到结点1的路径为
6-＞3-＞2-＞1，从根结点到结点5的路径为6-＞3-＞5)；然后遍历这两条路径，只要是相等的结点都是它们
的父结点，找到最后一个相等的结点即为离它们最近的共同父结点，在这个例子中，结点3就是它们共同的父
结点。示例代码如下：
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
class stack:
#模拟栈
def __init__(self):
self.items=[]
#判断栈是否为空
def isEmpty(self):
return len(self.items)==0
#返回栈的大小
def size(self):
return len(self.items)
#返回栈顶元素
def peek(self):
if not self.isEmpty():
return self.items[len(self.items)-1]
else:
return None
#弹栈
def pop(self):
if len(self.items)＞0:
return self.items.pop()
else:
print "栈已经为空"
return None
#压栈
def push(self,item):
self.items.append(item)
"""
方法功能: 获取二叉树从根结点root到node结点的路径
输入参数: root:根结点; node:二叉树中的某个结点; s:用来存储路径的栈返回值: node在root的予树上, 或
node==root时返回true, 否则返回false
"""
def getPathFromRoot(root,node,s):
if root==None:
return False
if root==node:
s.push(root)
return True
"""
如果node结点在root结点的左予树或右子树上,
那么root就是node的祖先结点, 把它加到栈里
"""
if getPathFromRoot(root.lchild, node,s) or getPathFromRoot(root.rchild, node,s):
s.push(root)
return True
return False
"""
方法功能: 查找二叉树中两个结点最近的共同父结点
输入参数: root:根结点;node1与node2为二叉树中两个结点
返回值: node1与node2最近的共同父结点
"""
def FindParentNode(root,node1,node2):
stack1=stack() #保存从root到node1的路径
stack2=stack()# 保存从root到node2的路径
#获取从root到node1的路径
getPathFromRoot(root, node1,stack1)
#获取从root到node2的路径
getPathFromRoot(root, node2, stack2)
commonParent=None
#获取最靠近node1和node2的父结点
while stackl.peek()==stack2.peek():
commonParent=stack1.peek()
stack1.pop()
stack2.pop()
return commonParent
if __name__=="__main__":
arr=[1,2,3,4,5,6,7,8,9,10]
root=arraytotree(arr,0,len(arr)-1)
node1=root.lchild.lchild.lchild
node2=root.lchild.rchild
res=None
res=FindParentNode(root,node1,node2)
if res!=None:
print str(node1.data)+"与"+str(node2.data)+"的最近公共父结点为:"+str(res.data),
else:
print "没有公共父结点"
程序的运行结果为：
1与5的最近公共父结点为：3
算法性能分析：
当获取二叉树从根结点root到node结点的路径时，最坏的情况就是把树中所有结点都遍历了一遍，这个操
作的时间复杂度为O(N)，再分别找出从根结点到两个结点的路径后，找它们最近的公共父结点的时间复杂度
也为O(N)，因此，这种方法的时间复杂度为O(N)。此外，这种方法用栈保存了从根结点到特定结点的路径，
在最坏的情况下，这个路径包含了树中所有的结点，因此，空间复杂度也为O(N)。
很显然，这种方法还不够理想。下面介绍另外一种能降低空间复杂度的方法。
方法二：结点编号法
根据性质，可以把二叉树看成是一棵完全二叉树(不管实际的二叉树是否为完全二叉树，二叉树中的结点都
可以按照完全二叉树中对结点编号的方式进行编号)，下图为对二叉树中的结点按照完全二叉树中结点的编号
方式进行编号后的结果，结点右边的数字为其对应的编号。
根据性质可以知道，一个编号为n的结点，它的父亲结点的编号为n/2。假如要求node1与node2的最近的
共同父结点，首先把这棵树看成是一棵完全二叉树(不管结点是否存在)，分别求得这两个结点的编号n1，
n2。然后每次找出n1与n2中较大的值除以2，直到n1==n2为止，此时n1或n2的值对应结点的编号就是它们
最近的共同父结点的编号，接着可以根据这个编号信息找到对应的结点，具体方法为：通过观察二叉树中结
点的编号可以发现：首先把根结点root看成1，求root的左孩子编号的方法为把root对应的编号看成二进制，
然后向左移一位，末尾补0，如果是root的右孩子，那么末尾补1，因此，通过结点位置的二进制码就可以确
定这个结点。例如结点3的编号为2(二进制10)，它的左孩子的求解方法为：10，向左移一位末尾补0，可以
得到二进制100(十进制4)，位置为4的结点的值为2。从这个特性可以得出通过结点位置信息获取结点的方
法，例如要求位置4的结点，4的二进制码为100，由于1代表根结点，接下来的一个0代表是左子树
root.lcluld，最后一个0也表示左子树root.lchild.lchild，通过这种方法非常容易根据结点的编号找到对应的
结点。实现代码如下：
import math
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
#方法功能: 把有序数组转换为二叉树
def arraytotree(arr,start,end):
root=None
if end＞=start:
root =BiTNode()
mid=(start+end+1)/2
#树的根结点为数组中问的元素
root.data=arr[mid]
#递归的用左半部分数组构造root的左子树
root.lchild=arraytotree(arr,start,mid-1)
#递归的用右半部分数组构造root的右予树
root.rchild=arraytotree(arr, mid+1, end)
else:
root=None
return root
class IntRef:
def __init__(self):
self.num=None
"""
方法功能: 找出结点在二叉树中的编号
输入参数: root:根结点node:待查找结点; number: node结点在二叉树中的编号
返回值: true:找到该结点的位置, 否则返回false
"""
def getNo(root,node,number):
if root==None:
return False
if root==node:
return True
tmp=number.num
number.num=2*tmp
#node结点在root的左子树中, 左子树编号为当前结点编号的2倍
if getNo(root.lchild, node, number):
return True
#node结点在root的右子树中,右子树编号为当前结点编号的2倍加1
else:
number.num=tmp*2+1
return getNo(root.rchild, node, number)
"""
方法功能: 根据结点的编号找出对应的结点
输入参数: root:根结点; number为结点的编号
返回值: 编号为number对应的结点
"""
def getNodeFromNum(root,number):
if root==None or number＜0:
return None
if number=1:
return root
#结点编号对应二进制的位数(最高位一定为1, 因为根结点代表1)
lens=int((math.log(number)/math.log(2)))
#去掉根结点表示的1
number-=1＜＜lens
while lens＞0:
#如果这一位二进制的值为1,
#那么编号为number的结点必定在当前结点的右子树上
if(1＜＜(lens-1))& number==1:
root=root.rchild
else:
root=root.lchild
lens-=1
return root
"""
方法功能: 查找二叉树中两个结点最近的共同父结点
输入参数: root:根结点;node1与node2为二叉树中两个结点
返回值: node1与node2最近的共同父结点
"""
def FindParentNode(root,node1,node2):
ref1=IntRef()
ref1.num=1
ref2=IntRef()
ref2.num=1
getNo(root, node1, ref1)
getNo(root, node2, ref2)
num1=ref1.num
num2=ref2.num
#找出编号为num1和num2的共同父结点
while num1!=num2:
if num1＞num2:
num1/=2
else:
num2/=2
#num1就是它们最近的公共父结点的编号, 通过结点编号找到对应的结点
return getNodeFromNum(root,num1)
if __name__=="__main__":
arr=[1,2,3,4,5,6,7,8,9,10]
root=arraytotree(arr,0,len(arr)-1)
node1=root.lchild.lchild.lchild
node2=root.lchild.rchild
res=None
res=FindParentNode(root,node1,node2)
if res!=None:
print str(nodel.data)+"与"+str(node2.data)+"的最近公共父结点为: "+str(res.data),
else:
print "没有公共父结点"
算法性能分析：
这种方法的时间复杂度也为O(N)，与方法一相比，在求解的过程中只用了个别的几个变量，因此，空间复
杂度为O(1)。
方法三：后序遍历法
很多与二叉树相关的问题都可以通过对二叉树的遍历方法进行改装而求解。对于本题而言，可以通过对二
叉树的后序遍历进行改编而得到。具体思路为：查找结点node1与结点node2的最近共同父结点可以转换为
找到一个结点node，使得node1与node2分别位于结点node的左子树或右子树中。例如题目给出的图中，
结点1与结点5的最近共同父结点为结点3，因为结点1位于结点3的左子树上，而结点5位于结点3的右子树
上。实现代码如下：
def FindParentNode(root,node1,node2):
if None==root or root==node1 or root==node2:
return root
lchild=FindParentNode(root.lchild, node1, node2)
rchild=FindParentNode(root.rchild, node1, node2)
#root的左子树中没有结点node1和node2,那么一定在root的右予树上
if None==lchild:
rerurn rchild
#root的右子树中没有结点node1和node2,那么一定在root的左子树上
elif None==rchild:
return lchild
#node1与node2分别位于root的左子树与右子树上, root就是它们最近的共同父结点
else:
return root
把方法一中的FindParentNode替换为本方法的FindParentNode，可以得到同样的输出结果。
算法性能分析：
这种方法与二叉树的后序遍历方法有着相同的时间复杂度O(N)。
');
![\"360截图20190815221550861.jpg\"](\"http://www.alatiku.com/d/file/shiti/1ee18ba991d791c284e0612dc0a141eb.jpg\")