赞
踩
此题想法比较简单,但是我遇到了一个坑。值得mark。首先介绍思想,这题是给一个N,然后让输出所有的二分树,首先偶数的N是不可能有结果的,试一下就知道,然后对于奇数,就采用递归的思想,将N-1分给左右两边,然后当作子问题去求解。这里因为会有许多重复的计算,所以借鉴记忆化dp的思想,声明一个数组来记录一下每次的树结构,避免重复计算。
大坑:一开始我是在循环外面定义root = TreeNode(0)的,然后一开始发现结果是两个一样的没有null的结果,我错误地以为是因为程序错误没有把null写出来?一直在纠结这个问题,后来我发现原来我输出的结果全都是一样的。仔细想了一下,我才想到,我们最后是将root添加进数组,我想当然地以为是将整个结构记录下来,仔细想一下,list中全都是root,当root这个对象定义的时候,它的指针就已经固定了,我不断更新的只是它的left和right。最后得到结果也只是通过root来向下遍历,因为root这个指针是固定的,所以最后遍历出来的肯定都是最后一次更新的left和right,也就导致了结果是一样的。所以应该每次记录root时,定义一个新的对象,使指针不同,这样的话就使得每个树状结构时独立的,在遍历的时候也就从不同的root(指针不同)来进行遍历,得到结果。貌似之前我也犯过这种错误,引以为戒。要多想想最后结果是通过什么得到的,不要想当然。
record = {}
class Solution:
def allPossibleFBT(self, N):
"""
:type N: int
:rtype: List[TreeNode]
"""
result = []
if N%2 == 0:
return result
if N == 1:
temp = [TreeNode(0)]
record[0] = temp
return temp
for i in range(1,N,2):
temp1 = []
temp2 = []
if record.get(i-1) != None:
temp1 = record.get(i-1)
else:
temp1 = self.allPossibleFBT(i)
if record.get(N-i-1-1) != None:
temp2 = record.get(N-i-1-1)
else:
temp2 = self.allPossibleFBT(N-i-1)
for m in temp1:
for n in temp2:
root = TreeNode(0)
root.left = m
root.right = n
result.append(root)
return result
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。