一个在树状或图状结构里面查找东西,或者返回某条路径,很容易想到使用递归.

比如说下面这个例子,node是一个链表结构,pre属性链接前一个节点,next属性链接后一个节点.我们只知道节点Node1,需要返回该节点下链接的所有节点.用递归很容易实现这个需求:

def getPath(self, node, path):
	path.append(node)

	if node.next is None:
		return path

	return getPath(node.next, path)


getPath(Node1,[])

但是这里使用递归有效率问题,假如递归了N次,我们会创建N个path变量,长度分布是1,2,3,…,N.

更糟糕的是递归有深度限制,当数据量比较大的时候会报错.

这种情况通常使用循环来替代递归:

def getPath(self, node):
	path = []

	while node.next != None:
		path.append(node)
		node = node.next
		
	path.append(node)
	return path


getPath(Node1)
posted @ 2018-09-14 20:28:45
评论加载中...

发表评论