1
class Solution:
2
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
3
        if root == None:
4
            return 0
5

6
        N = 3 * 10000 + 10
7
        ans = -N * 1000
8

9
        s = dict()
10

11
        def dfs(u):
12
            nonlocal ans
13
            if u.left is None:
14
                s[(u, 0)] = 0
15
            if u.right is None:
16
                s[(u, 1)] = 0
17
            if u.left:
18
                dfs(u.left)
19
                s[(u, 0)] = max(0, max(s[(u.left, 0)], s[(u.left, 1)]) + u.left.val)
20
            if u.right:
21
                dfs(u.right)
22
                s[(u, 1)] = max(0, max(s[(u.right, 0)], s[(u.right, 1)]) + u.right.val)
23
            ans = max(ans, u.val + s[(u, 0)] + s[(u, 1)])
24

25
        dfs(root)
26

27
        return ans

1
class Solution:
2
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3
        if root is None or root == p or root == q:
4
            return root
5

6
        l = self.lowestCommonAncestor(root.left, p, q)
7
        r = self.lowestCommonAncestor(root.right, p, q)
8

9
        if l and r:
10
            return root
11
        if l:
12
            return self.lowestCommonAncestor(l, p, q)
13
        if r:
14
            return self.lowestCommonAncestor(r, p, q)
15
        return None