Definition for a binary tree node.

class TreeNode(object):

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left or right

def pathSum(self, root, node, path):
    if not root:
        return False
    path.append(root)
    if root == node:
        return True
    if (root.left and self.pathSum(root.left, node, path)) or (root.right and self.pathSum(root.right, node, path)):
        return True
    path.pop()
    return False

def estimateTransmissions(self, root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: int
    """
    lca = self.lowestCommonAncestor(root, p, q)
    path1, path2 = [], []
    self.pathSum(lca, p, path1)
    self.pathSum(lca, q, path2)
    path = path1 + path2[::-1]
    res = 0
    for i in range(1, len(path)):
        res += (1 << (i - 1))
    return res