我正在尝试解决查找节点距离 K 的问题。我将发布问题陈述。
给定二叉树的根节点、树中包含的节点的目标值以及正整数 k。编写一个函数，返回与目标值节点距离恰好为 k 的所有节点的值。两个节点之间的距离定义为从一个节点出发必须遍历的边数 节点到另一个。
我的逻辑是一步一步地工作。首先，我编写了一个函数来查找目标节点。 接下来，我分配了所有父节点，创建了一个字典来分配所有父节点。最后，我创建了一个辅助函数，它递归地遍历所有节点，直到达到 None 或 k 为负 作为我的基本情况。很快就知道我将进入无限循环，因为我正在遍历三种方式
如果我没有保留访问安全系统，我会继续来回访问很多节点。
我编写了一个访问系统，我过早地将其标记为已访问，即在节点上调用递归函数，标记已访问的节点，在另一个节点上调用递归。我的想法是，如果节点无法访问同一节点，它将停止进入无限循环。但无限循环仍然存在。我想要一个解释为什么。谢谢你。
我的代码：
class BinaryTree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def findNodesDistanceK(tree, target, k):
targetNode = findtargetNode(tree, target)
nodeToParents = {tree: None}
nodeToParents = assignParentnodes(tree, nodeToParents)
#for ele in nodeToParents:
# if nodeToParents[ele]:
# print(ele.value, nodeToParents[ele].value)
# else:
# print(ele.value, nodeToParents[ele])
runningList = list()
visited = list()
nodes = helper(targetNode, k, nodeToParents, runningList, visited)
toReturn = list()
for ele in nodes:
if ele.value != target:
toReturn.append(ele.value)
if target in toReturn:
toReturn.remove(target)
setreturn = set(toReturn)
return list(setreturn)
def helper(node, k, parents, runningList, visited):
if node is None or k < 0:
return []
if node is not None and k == 0:
runningList.append(node)
return runningList
if node in visited:
return runningList
#visited.append(node)
clist = list()
alist = list()
blist = list()
if parents[node] is not None:
clist = helper(parents[node], k-1, parents, runningList, visited)
# visited.append(parents[node])
alist = helper(node.left, k-1, parents, runningList, visited)
blist = helper(node.right, k-1, parents, runningList, visited)
runningList.extend(alist)
runningList.extend(blist)
runningList.extend(clist)
visited.append(node)
return runningList
def findtargetNode(node, target):
if not node:
return node
if node.value == target:
return node
leftnode = findtargetNode(node.left, target)
rightnode = findtargetNode(node.right, target)
if rightnode is None:
return leftnode
return rightnode
def assignParentnodes(node, dictionary):
if node is None:
return dictionary
if node.left:
dictionary[node.left] = node
if node.right:
dictionary[node.right] = node
assignParentnodes(node.left, dictionary)
assignParentnodes(node.right, dictionary)
return dictionary
它不会涉及递归问题，但是当我将其添加回去时，它会涉及递归问题。
无限循环的测试用例失败：
{
"nodes": [
{"id": "1", "left": "2", "right": "3", "value": 1},
{"id": "2", "left": "4", "right": null, "value": 2},
{"id": "3", "left": null, "right": "5", "value": 3},
{"id": "4", "left": "6", "right": null, "value": 4},
{"id": "5", "left": "7", "right": "8", "value": 5},
{"id": "6", "left": null, "right": null, "value": 6},
{"id": "7", "left": null, "right": null, "value": 7},
{"id": "8", "left": null, "right": null, "value": 8}
],
"root": "1"
}
target:6
k:17
我的思考过程是，即使我在让它首先探索其他邻居/子节点等之前过早地将节点标记为已访问，函数不会过早返回吗？当然，这不是准确的解决方案，但是是什么导致了无限循环呢？您建议修复什么？在它探索了所有邻居后，我应该将其标记为已访问吗？感谢任何帮助。
测试代码
import program
import unittest
class TestProgram(unittest.TestCase):
def test_case_1(self):
root = program.BinaryTree(1)
root.left = program.BinaryTree(2)
root.right = program.BinaryTree(3)
root.left.left = program.BinaryTree(4)
root.left.left.left = program.BinaryTree(6)
root.right.right = program.BinaryTree(5)
root.right.right.left = program.BinaryTree(7)
root.right.right.right = program.BinaryTree(8)
target = 6
k = 17
expected = []
actual = program.findNodesDistanceK(root, target, k)
actual.sort()
self.assertCountEqual(actual, expected)
问题在于，您不断对已访问过的节点进行递归调用，从而允许搜索路径在父级和子级之间上下移动，并且当来自更深或更高的节点时重复相同的上下移动。这使得搜索路径的数量呈指数级增长，并且还会收集结果列表中重复且不一定相距较远的节点𝑘。
这并不是一个真正的“无限”长的过程，但无论是在内存还是时间方面，它都很快变得天文数字。例如，如果将示例情况中的 k 更改为 8，则预期结果是空列表，但如果让程序运行足够长的时间，它会返回 [2, 3, 7, 8]，这显然是错误的。对于 𝑘 等于 10，等待和内存使用量变得很大，而对于 𝑘 等于 17，搜索需要太多时间和资源才能正常完成。
所以改变这个：
if node is not None and k == 0:
runningList.append(node) # This should NOT be done when node already visited
return runningList
if node in visited:
return runningList
clist = list()
alist = list()
blist = list()
if parents[node] is not None:
clist = helper(parents[node], k-1, parents, runningList, visited)
alist = helper(node.left, k-1, parents, runningList, visited)
blist = helper(node.right, k-1, parents, runningList, visited)
visited.append(node) # <-- this happens too late!
对此：
if node in visited: # Do this before recursive calls and before appending
return runningList
visited.append(node) # And then immediately mark as visited
if node is not None and k == 0:
runningList.append(node)
return runningList
clist = list()
alist = list()
blist = list()
if parents[node] is not None:
clist = helper(parents[node], k-1, parents, runningList, visited)
alist = helper(node.left, k-1, parents, runningList, visited)
blist = helper(node.right, k-1, parents, runningList, visited)
这将解决您的问题。
请注意，您可以大大缩短代码。
您实际上并不需要findtargetNode
nodeToParent
helperyields找到的节点。
visiteddef findNodesDistanceK(tree, target, k):
nodeToParents = assignParentnodes(tree, {tree: None})
targetNode = next((node for node in nodeToParents if node.value == target), None)
nodes = helper(targetNode, k, nodeToParents, set())
return [ele.value for ele in nodes]
def helper(node, k, parents, visited):
if k < 0 or not node or node in visited:
return
visited.add(node)
if k == 0:
yield node
else:
yield from helper(parents[node], k-1, parents, visited)
yield from helper(node.left, k-1, parents, visited)
yield from helper(node.right, k-1, parents, visited)
def assignParentnodes(node, dictionary):
if node is None:
return dictionary
if node.left:
dictionary[node.left] = node
if node.right:
dictionary[node.right] = node
assignParentnodes(node.left, dictionary)
assignParentnodes(node.right, dictionary)
return dictionary