convert bst to greater tree

这道题我一开始没看清是BST,以为只是普通binary tree. 一开始觉得会很麻烦,后来发现是BST,那么要find all the keys greater than current one, 那不是只要把他right sub tree sum起来加到current 上不就好了

但是写完发现test case并不对。 恍然大悟, 比如 5 2 13这个case。 2右下角什么都没有,但是他会变成18. 因为他和其他所有key的差距就是他的爸爸加上 all the keys greater than 他爸爸。 因为他爸爸本来就比他大,再加上其他所有比他爸爸大的key,这些都要加进来。


于是,我就这么做了。 但是发现。。妈的 还是不对。 不能简单直接把parent key加到right child上,因为爸爸没有right child大。 可是!万一爷爷比right child大,那不是得加进来了。于是我做了一个我觉得还蛮聪明的trick。

不好描述。。。看代码吧 就是一个参数。


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

推荐阅读更多精彩内容