二叉树最大值和最小值的距离

思路:

1. 找到最大值和最小值；
2. 找到这两个值的最低公共祖先；
3. 计算各自到最低公共祖先的距离；
4. 将距离相加return。

# 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 solve(self, root):
        self._max = float("-inf")
        self._min = float("inf")
        self.getMax(root)
        self.getMin(root)
        lcm = self.getLCM(root, self._max, self._min)
        n1 = self.getLength(lcm, self._min)
        n2 = self.getLength(lcm, self._max)
        return n1 + n2

    def getLength(self, root, p):
        queue = [root]
        level = 0
        while queue:
            n = len(queue)
            for i in range(n):
                cur = queue.pop(0)
                if cur.val == p:
                    return level
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            level += 1

    def getLCM(self, root, p, q):
        if not root:
            return None
        if root.val == p or root.val == q:
            return root
        left =  self.getLCM(root.left, p, q)
        right =  self.getLCM(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        if left and right:
            return root

    def getMax(self, root):
        queue = [root]
        while queue:
            cur = queue.pop(0)
            if cur.val > self._max:
                self._max = cur.val
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)

    def getMin(self, root):
        queue = [root]
        while queue:
            cur = queue.pop(0)
            if cur.val < self._min:
                self._min = cur.val
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)

node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(0)
node6 = TreeNode(6)
node7 = TreeNode(7)

node1.left = node2
node1.right = node3

node2.left = node4
node2.right = node5

node3.left = node6
node3.right = node7

s = Solution()
res = s.solve(node1)
print(res)