给定一棵二叉树的根节点 root 以及两个整数 p 和 q ，返回该二叉树中值为 p 的结点与值为 q 的结点间的 距离 。
两个结点间的 距离 就是从一个结点到另一个结点的路径上边的数目。
示例 1：
image.png
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0
输出：3
解释：在 5 和 0 之间有 3 条边：5-3-1-0
示例 2：
image.png
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7
输出：2
解释：在 5 和 7 之间有 2 条边：5-2-7
示例 3：
image.png
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5
输出：0
解释：一个结点与它本身之间的距离为 0
提示：
树中结点个数的范围在 [1, 104].
0 <= Node.val <= 109
树中所有结点的值都是唯一的.
p 和q 是树中结点的值.
分析此题无非就是把二叉树转成图，再用最短路径算法求出最小路径
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val = 0, left = nil, right = nil)
# @val = val
# @left = left
# @right = right
# end
# end
# @param {TreeNode} root
# @param {Integer} p
# @param {Integer} q
# @return {Integer}
def find_distance(root, p, q)
if p == q
return 0
end
@graph = {}
tree_to_graph(root)
h = {}
@graph.each_pair do |k,v|
h[k] = {}
v.each do |v1|
h[k][v1] = 1
end
end
m = dijkstra(h,p)
m[q]
end
def tree_to_graph(node)
return @graph if node.nil?
@graph[node.val] ||= []
if node.left
@graph[node.left.val] ||= []
@graph[node.val] << node.left.val
@graph[node.left.val] << node.val
tree_to_graph(node.left)
end
if node.right
@graph[node.right.val] ||= []
@graph[node.val] << node.right.val
@graph[node.right.val] << node.val
tree_to_graph(node.right)
end
end
def dijkstra(graph, source)
dist = Hash.new(Float::INFINITY)
dist[source] = 0
pq = Containers::PriorityQueue.new
pq.push(source, 0)
until pq.empty?
u = pq.pop
graph[u].each do |v, weight|
if dist[v] > dist[u] + weight
dist[v] = dist[u] + weight
pq.push(v, -dist[v])
end
end
end
dist
end
