思路:
- 找到最大值和最小值；
- 找到这两个值的最低公共祖先；
- 计算各自到最低公共祖先的距离；
- 将距离相加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)
