question 1:
我的方法:
问题:
这种方法值比较上下两个节点间的差值,但是如果超过节点间不是子父节点的关系的话就无法比较了。所以过不了
别人的方法:
遍历整个树,将树转换成列表
对列表进行排序,求出最小的相邻元素的差值
这种方法对于任意树都可以,因为得到列表后再排序,所以即使不是搜索树也可以用这种方法
question 2
别人的方法:
实际上这是个数学问题,因为要求每次有n-1个数要加1而且最后的结果是所有的数要相等,所以作为列表中最小的数必须要每一次都参加。假设m次能够使得全部的数相等(都为x)
sum(nums) +m*(n-1)=x*n
x=minNums +m
解出答案 m = sum(nums) - n*minNums
证明为什么最小数每一次都要参加
question 3
给定一个树,求每个节点的所有左子节点的和减去右子节点的和的绝对值。返回所有绝对值的和
我的答案:
根据题目要求,要得到所有子节点的和,所以需要定义函数来计算子节点的和。得到了子节点的和以后,根据要求,计算和的差值,再累加
缺点:非常的慢。注意上面每次循环的递归次数。同时注意到getnodesum与得到子节点的findTilt其实大部分操作都不冲突,可以将这两个递归合并起来
别人的方法:
效果:速度比改进前快5倍