最近公共祖先问题

如题，直接上代码

这次这个是从学长那边打听到的面试的题目以及自己在做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。

这里再额外提供一个示例测试用例：