这道题我一开始没看清是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。
不好描述。。。看代码吧 就是一个参数。