有没有办法找到二叉树中每个节点的最远节点。我知道树的直径问题，但那是查询每个节点的问题。我希望有一种算法适用于n个节点的树，并且时间复杂度为 O(nlogn)。
每个节点的最远节点
3
- Michocio
5
有向树还是无向树？ - UmNyobe
最遠的節點，是指距離所有其他節點最遠的節點嗎？ - Dirk Horsten
@UmNyobe 无向的。 - Michocio
@Dirk Horsten 对于每个节点，它都可以是另一个节点。 - Michocio
你是否对边缘应用权重？ - Dirk Horsten
2个回答
3
在两个步骤中：
1. 计算每个节点的最远子节点及其距离。这可以通过后序遍历树（O(n)）完成。 2. 对于每个节点：检查该节点的最远子节点以及其每个父节点（向根走时添加一额外距离）。选择最大值。O(n logn)。
修改：如果您存储了左右子树的最远子节点及其距离，可以按照前序遍历树并在O(n)时间内获得所有结果。
示例（不带标记哪个节点是最远节点..实现细节）：
1. 计算每个节点的最远子节点及其距离。这可以通过后序遍历树（O(n)）完成。 2. 对于每个节点：检查该节点的最远子节点以及其每个父节点（向根走时添加一额外距离）。选择最大值。O(n logn)。
修改：如果您存储了左右子树的最远子节点及其距离，可以按照前序遍历树并在O(n)时间内获得所有结果。
示例（不带标记哪个节点是最远节点..实现细节）：
3.2 root
/ \
1*2 0.1
/ \ \
0.0 1.1 0.0
/ \
0.0 0.0
从根开始 - 父节点的最长距离为0。
- 最长距离是max(0,2,3) = 3。
- 向左递归：将max(0,2)+1作为通过父节点的最长距离传递。
- 向右递归：将max(0,3)+1作为通过父节点的最长距离传递。
在任何时刻，有三种可能性：最长路径经过父节点，位于左子树或右子树。当访问节点时，所有这些距离都是容易获得的。
- Karoly Horvath
6
预订？请提供详细信息。 - UmNyobe
好的，这是基于假设你不能向上移动的情况。否则，你需要进行两次运算。首先计算每个节点的d(left)和d(right)，然后执行
d = min(d(left), d(right), parent.left == this ? parent.d(parent.right) : parent.d(parent.left))。 - UmNyobe@Karoly Horvath，你只限制在二叉树上了。这是必要的吗？ - Dirk Horsten
@DirkHorsten：不可否认，OP的问题确实是这样说的：“有没有办法找到二叉树中每个节点的最远节点？” - AndyG
@DirkHorsten：既然处理其他情况很简单，那么这并不是问题。事实上，你可以将计数推迟一级，从而降低成本。 - Karoly Horvath
抱歉，我不完全理解那个解决方案的想法。假设我想要一个处理最远节点和每个节点距离的数字数组。@KarolyHorvath，能否再给一个例子？拜托了 :) - Michocio
0
对于那些对Karolys解决方案感兴趣的Python实现：
步骤1：向下搜索
- 对于每个节点和它的每个子节点，计算最远的孙子。
- 对于每个节点，记住我们以这种方式找到的两个最长的分支。
Python代码：
def getFarGrandChild(node, tree, grandChildren):
winner = None # {'node' : node, 'distance' : 0}
second = None
for child in tree.childrenOf(node):
grandChild = getFarGrandChild(child, tree, grandChildren)
if winner == None or grandChild['distance'] > winner['distance']:
second = winner
winner = grandChild
elif second == None or grandChild['distance'] > second['distance']:
second = grandChild
grandChildren[node] = (winner, second)
if winner == None:
return {'child' : node,
'grandChild' : node,
'distance' : 1}
else:
return {'child' : node,
'grandChild' : winner['grandChild'],
'distance' : winner['distance'] + 1}
步骤2：在所有方向上搜索
A与其子代和孙代相连，也与其父代、祖先及其它后代相连。我们称这些为侄女
- 对于根节点，选择最远的节点作为最远节点：最远的子节点。
- 对于每个子节点，选择最远的子节点或最远的侄女。 最远的侄女是来自另一个分支中距离根节点最远的子节点。
- 向下进行，最远的侄女现在可以来自另一个子节点或更高层次。
Python代码：
def getFarRelative(node, tree, grandChildren, farNodes, niece = None):
winner, second = grandChildren[node]
if niece != None:
if winner == None or niece['distance'] > winner['distance']:
second = winner
winner = niece
elif second == None or niece['distance'] > second['distance']:
second = niece
farNodes[node] = winner
for child in tree.childrenOf(node):
if child != winner['child']:
getFarRelative(child, tree, grandChildren, farNodes,
niece = {'child' :node,
'grandChild' : winner['grandChild'],
'distance' : winner['distance'] + 1})
elif second != None:
getFarRelative(child, tree, grandChildren, farNodes,
niece = {'child' : node,
'grandChild' : second['grandChild'],
'distance' : second['distance'] + 1})
我创建了我的树
使用以下代码通过from graph import *
# A set of data structures to represent graphs
#
class Node(object):
def __init__(self, name):
self.name = str(name)
def getName(self):
return self.name
def __str__(self):
return self.name
def __repr__(self):
return self.name
def __eq__(self, other):
return self.name == other.name
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
# Override the default hash method
# Think: Why would we want to do this?
return self.name.__hash__()
class Edge(object):
def __init__(self, src, dest):
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return '{0}->{1}'.format(self.src, self.dest)
class Digraph(object):
"""
A directed graph
"""
def __init__(self):
# A Python Set is basically a list that doesn't allow duplicates.
# Entries into a set must be hashable (where have we seen this before?)
# Because it is backed by a hashtable, lookups are O(1) as opposed to the O(n) of a list (nifty!)
# See http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset
self.nodes = set([])
self.edges = {}
def addNode(self, node):
if node in self.nodes:
# Even though self.nodes is a Set, we want to do this to make sure we
# don't add a duplicate entry for the same node in the self.edges list.
raise ValueError('Duplicate node')
else:
self.nodes.add(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.nodes
def __str__(self):
res = ''
for k in self.edges:
for d in self.edges[str(k)]:
#for d in self.edges[k]:
res = '{0}{1}->{2}\n'.format(res, k, d)
return res[:-1]
并在此树上进行测试
if __name__ == '__main__':
# Create a tree :
# root
# / \
# l r
# / \
# ll lr
# / \
# lll lrr
# /
# llll
myTree = Digraph()
myTree.addNode(Node(str('root')))
myTree.addNode(Node(str('l'))) # for left
myTree.addEdge(Edge(Node(str('root')), Node(str('l'))))
myTree.addNode(Node(str('ll'))) # for left, left
myTree.addEdge(Edge(Node(str('l')), Node(str('ll'))))
myTree.addNode(Node(str('lll')))
myTree.addEdge(Edge(Node(str('ll')), Node(str('lll'))))
myTree.addNode(Node(str('llll')))
myTree.addEdge(Edge(Node(str('lll')), Node(str('llll'))))
myTree.addNode(Node(str('lr'))) # for left, right
myTree.addEdge(Edge(Node(str('l')), Node(str('lr'))))
myTree.addNode(Node(str('lrr')))
myTree.addEdge(Edge(Node(str('lr')), Node(str('lrr'))))
myTree.addNode(Node(str('r')))
myTree.addEdge(Edge(Node(str('root')), Node(str('r'))))
通过这些语句
grandChildren = {}
getFarGrandChild(Node('root'), myTree, grandChildren)
for key in grandChildren:
print key, grandChildren[key]
print '\n'
farNodes = {}
getFarRelative(Node('root'), myTree, grandChildren, farNodes)
print '\n'
for key in farNodes:
print key, farNodes[key]
- Dirk Horsten
1
感谢挑战，Karoly和Michocio。 - Dirk Horsten
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接