在二叉树中找到两个节点的最近公共祖先

[编程题]在二叉树中找到两个节点的最近公共祖先

热度指数：1790 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

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

最后一行为节点 o1 和 o2。

输出描述:

输出一个整数表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

Python

歪比歪比阿嘛鸿

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p:int, q:int) -> 'TreeNode':
        if not root&nbs***bsp;root.val == p&nbs***bsp;root.val == q:return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if left:return left
        if right:return right
 

if __name__ == '__main__':
    n, root_val = map(int, input().split())
    node_key = {}
    lst = []
    for i in range(n):
        v, l, r = map(int, input().split())
        lst.append((v ,l, r))
        node_key[v] = TreeNode(v)
        if i == 0:root = node_key[v]
    for v, l, r in lst:
        if l:
            node_key[v].left = node_key[l]
        if r:
            node_key[v].right = node_key[r]
    p, q = map(int, input().split())
    node = Solution().lowestCommonAncestor(root, p, q)
    print(node.val)

发表于 2021-08-02 19:48:34 回复(0)