[easy+][Tree] 563.Binary Tree Tilt

原题是:

Screen Shot 2017-11-06 at 3.33.12 PM.png

思路是:

我一开始的思路是:第一步,写两个函数,第一个函数对一个给定的root,求以它为root的这棵树的节点val的和。 第二个函数,求root这个节点的tilt。并把它上的val更新为tilt.

第二步,用第一个所写的求和函数,将整颗树上所有的tilt值的和求出来。

那么这个思路,虽然可行,但是有一个很大的时间上的浪费,就是从上至下,进行了太多的重复计算。每个节点,都要计算他左右子树的val的和。

那么一个重要的技巧是,函数是可以返回多个值得。将从下到上的每次所得的tilt的和,和元素之和,同时都返回,代入到上一层节点的计算中。就可以避免大量的重复计算。

代码是:

Screen Shot 2017-11-06 at 3.40.43 PM.png

在这之前有一版结果正确但是超时的代码,问题在于多次调用了process这个helper函数,而没有用变量将所得到的值,存起来,导致的超时。递归的代码,一定要注意这一点。


Screen Shot 2017-11-06 at 3.42.24 PM.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容