题解 | #两个链表生成相加链表#

'''
解题思路：
1、先dfs搜索，返回节点路径
2、取路径交集返回最近的交点
'''
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
def dfs(root,o1,res):
    if root.val == o1:
        #print('res=',res)
        return res
    if root.left:
        t = dfs(root.left,o1,res+[root.left.val])
        if t:
            return t
    if root.right:
        t = dfs(root.right,o1,res+[root.right.val])
        if t:
            return t
            
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        L1 = dfs(root,o1,[root.val])
        L2 = dfs(root,o2,[root.val])      
        #print(L1)
        #print(L2)
        L1 = L1[::-1]
        L2 = L2[::-1]
        for i in L1:
            for j in L2:
                if i==j:
                    return i
        return None
    
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(Solution().lowestCommonAncestor(root,4,5))