160.相交链表

160

题解： 参考灵茶山艾府题解

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.next = None
 6
 7class Solution:
 8    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
 9        p1 = headA
10        p2 = headB
11        while p1 is not p2:
12            p1 = p1.next if p1 else headB
13            p2 = p2.next if p2 else headA
14        return p1

核心思想是两条链表满足 $(x+z)+y = (y+z)+x$，z为公共部分的长度

236.二叉树的最近公共祖先

236

题解：

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.left = None
 6#         self.right = None
 7
 8class Solution:
 9    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10        if root in (None, p, q):
11            return root
12        left = self.lowestCommonAncestor(root.left,p,q)
13        right = self.lowestCommonAncestor(root.right,p,q)
14        if left and right:
15            return root
16        return left or right