[LeetCode] 538. Convert BST to Greater Tree

轉自LeetCode

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

<Solution>

想法如下

• 這題的主要關鍵在於，是要把所有比自己數字大的數字和自身加起來，而BST的特性是，在右子樹的都一定比自身大，在左子樹的都一定比自身小

• 因此，對BST採用 右 -> 根 -> 左 的方式去歷遍，並且同時累加數字，歷遍完即可

code 如下

C++