class Solution:
def __init__(self):
self.prelist = list() def preTree(self,root:TreeNode):
if root != None:
self.preTree(root.left)
self.prelist.append(root.val)
self.preTree(root.right) def Construct(self,ary):
if len(ary)>0:
result = TreeNode(ary[0])
maxnum = ary[0]
maxindex = 0
for i in range(1,len(ary)):
if maxnum < ary[i]:
maxnum = ary[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(ary[:maxindex])
result.right = self.Construct(ary[maxindex+1:])
return result
else:
return None def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
prelist2 = list()
self.preTree(root)
prelist2 = self.prelist[:]
prelist2.append(val)
result = TreeNode(prelist2[0])
maxnum = prelist2[0]
maxindex = 0
for i in range(1,len(prelist2)):
if maxnum < prelist2[i]:
maxnum = prelist2[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(prelist2[:maxindex])
result.right = self.Construct(prelist2[maxindex+1:])
return result
注意第3行，这里是用构造函数来初始化了一个“成员变量”，这样是可以正常工作的。但是如果使用“类变量”，如下面的第2行，在oj上就会报错。
class Solution:
prelist = list()
def preTree(self,root:TreeNode):
if root != None:
self.preTree(root.left)
self.prelist.append(root.val)
self.preTree(root.right) def Construct(self,ary):
if len(ary)>0:
result = TreeNode(ary[0])
maxnum = ary[0]
maxindex = 0
for i in range(1,len(ary)):
if maxnum < ary[i]:
maxnum = ary[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(ary[:maxindex])
result.right = self.Construct(ary[maxindex+1:])
return result
else:
return None def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
self.preTree(root)
prelist2 = self.prelist[:]
prelist2.append(val)
result = TreeNode(prelist2[0])
maxnum = prelist2[0]
maxindex = 0
for i in range(1,len(prelist2)):
if maxnum < prelist2[i]:
maxnum = prelist2[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(prelist2[:maxindex])
result.right = self.Construct(prelist2[maxindex+1:]) return result
为了解决这个问题，还可以使用一种方式，就是把结果集合传递到前序遍历的方法中，如下面第2行定义的方法，多了一个prelist参数，用于记录结果：
class Solution:
def preTree(self,root:TreeNode,prelist):
if root != None:
self.preTree(root.left,prelist)
prelist.append(root.val)
self.preTree(root.right,prelist) def Construct(self,ary):
if len(ary)>0:
result = TreeNode(ary[0])
maxnum = ary[0]
maxindex = 0
for i in range(1,len(ary)):
if maxnum < ary[i]:
maxnum = ary[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(ary[:maxindex])
result.right = self.Construct(ary[maxindex+1:])
return result
else:
return None def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode:
prelist2 = list()
self.preTree(root,prelist2)
prelist2.append(val)
result = TreeNode(prelist2[0])
maxnum = prelist2[0]
maxindex = 0
for i in range(1,len(prelist2)):
if maxnum < prelist2[i]:
maxnum = prelist2[i]
maxindex = i
result.val = maxnum
result.left = self.Construct(prelist2[:maxindex])
result.right = self.Construct(prelist2[maxindex+1:])
return result
总结：使用第1种写法最为稳妥。