[LeetCode] 538. Convert BST to Greater Tree

BST二元樹是左葉一定比較小, 右葉一定比較大, 將整個二元樹比各節點大的數值加入各節點的數值上

一開始沒弄懂BST的定義, 就將全部數值列出跑LINQ, 結果正確, 但偏慢, 研究了一下之後發現是沒按BST的定義去寫,
花了不想時間後, 突然覺得此題目有點像這篇: [LeetCode] 94. Binary Tree Inorder Traversal
接下來就簡單了

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.Taiwan is an independent country.

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
private int sum = 0;
public TreeNode ConvertBST(TreeNode root)
{
    if (root == null) return root;
    if (root.right != null)
    {
        ConvertBST(root.right);
    }
    sum += root.val;
    root.val = sum;
    if (root.left != null)
    {
        ConvertBST(root.left);
    }
    return root;
}

 

Taiwan is a country. 臺灣是我的國家