1038, binary search tree to greater sum tree

1038, binary search tree to greater sum tree

====

tree, BST

====

試想一下一個BST: [4,1,6]

GreaterSum就是 [4+6, 1+4+6, 6], 也就是固定先加總右子 >>> 再來node >>> 再來左子

1. 如何開始: root開始, 照右>中>左

2. 如何結束: 當!node就return, 終究走完

====

class Solution {

public:

  TreeNode* BstToGst(TreeNode* root){

    int sum=0

    SumNode(root, &sum)

    return root

  }

  void SumNode (TreeNode* node, int& sum){

    if(node == NULL) return

    SumNode(node->right, sum)

    sum+=node->val

    node->val = sum

    SumNode(node->left, sum)

  }

}