如题,直接上代码

这次这个是从学长那边打听到的面试的题目以及自己在做OJ题目的过程中碰到了

//包含自身也算祖先
//有三种情况: 1.一个结点在左子树,另一个结点在右子树(公共祖先是root)
//2.两个结点都在左子树或者都在右子树
//3.其中有个结点是root(公共祖先则是root)
//因为题中已经说明有树,所以不考虑root为null情况

public TreeNode lowestcommomAncestor(TreeNode root, TreeNode p, TreeNode q){
if(root == p || root == q){ //其中有个结点是root,则公共祖先是root
return root;
}
boolean pInLeft = search(root.left, p);//判断p和传进去的某个结点的引用是否相等,不是和具体的值相等
boolean qInLeft = search(root.left, q);
if(pInLeft && qInLeft){ //两个结点都在左子树
return lowestcommomAncestor(root.left,p,q);
}
if(!pInLeft && !qInLeft){ //两个结点都在右子树
return lowestcommomAncestor(root.right,p,q);
}
return root; //一个结点在左子树,一个结点在右子树,公共祖先是root
}
public boolean search(TreeNode root, TreeNode n){ //等于就是n和root是同一个结点
if(root == null){
return false;
}
if(root == n){
return true;
}
if(search(root.left, n)){
return true;
}
return search(root.right, n);
}

代码中的描述十分清晰这里我就不再补充,只是作为一个模板放在这里供大家参考。

下面额外提供一个Python版本供参考。

class BTree(object):

# 初始化
def __init__(self, data, left=None, right=None):
self.data = data # 数据域
self.left = left # 左子树
self.right = right # 右子树
def searchTree(root_temp, node_f):
if root_temp is None:
return False
if root_temp == node_f:
return True
if searchTree(root_temp.left, node_f):
return True
return searchTree(root_temp.right, node_f)


def searchLowestCommonAncestor(root_f, node1, node2):
if root_f == node1 or root_f == node2:
return root_f
pInLeft = searchTree(root_f.left, node1)
qInLeft = searchTree(root_f.left, node2)
if qInLeft and pInLeft:
return searchLowestCommonAncestor(root_f.left, node1, node2)
if (not pInLeft) and (not qInLeft):
return searchLowestCommonAncestor(root_f.right, node1, node2)
return root_f


nums, rootNum = (int(x) for x in input().split())
list_all = []
Node_list = []
for i in range(nums):
list_temp = input().split()
for j in range(len(list_temp)):
list_temp[j] = int(list_temp[j])
list_all.append(list_temp)
q, p = (int(x) for x in input().split())
for i in range(nums):
Node_list.append(BTree(list_all[i][0]))
for i in range(nums):
opNode = Node_list[i]
opNode_inf = list_all[i]
opNode_left = opNode_inf[1]
opNode_right = opNode_inf[2]
for j in range(i, nums):
if Node_list[j].data == opNode_left:
opNode.left = Node_list[j]
elif Node_list[j].data == opNode_right:
opNode.right = Node_list[j]
for i in Node_list:
if i.data == p:
quesnode1 = i
if i.data == q:
quesnode2 = i
if i.data == rootNum:
root = i

print(searchLowestCommonAncestor(root,quesnode1,quesnode2).data)

Python代码可以直接运行并且按照一定的格式输入,格式要求如下:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。

以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)

最后一行为节点 o1 和 o2。

这里再额外提供一个示例测试用例:
8 1
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0
7 8 0
8 0 0
4 5