Runtime: 0 ms, faster than100.00%ofC++online submissions forBinary Search Tree to Greater Sum Tree.
Memory Usage: 9.6 MB, less than100.00%ofC++online submissions forBinary Search Tree to Greater Sum Tree.
LeetCode #1038
Q.
Given the root of a binarysearchtree with distinct values, modify it so that everynode has a new value equal to the sum of the values of the original tree that are greater than or equal tonode.val.
As a reminder, a binary search treeis a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
각기 다른 값들을 가진 이진트리의 루트노드가 주어지고, 기존의 노드값보다 크거나 같은 노도값들의 합과 같은 새 값으로 모두 바꾸어라.
The number of nodes in the tree is between1and100.
Each node will have value between0and100.
The given tree is a binary search tree.
Process
// Process //1. Input root node //2. Iterate 2-val-1 order in tree structure // 2.1. Make list of val //3. Make greaterSum list //4. Correct tree using value list //5. Return root node
// 처리과정
//1. 루트노드 입력받는다.
//2. 2-val-1 순서로 트리 순회한다.
// 2.1. value list 만든다.
//3. value list 를 greaterSum 적용한다.
//4. original tree 를 만들어둔 value list 값으로 바꾼다.
//5. rootNode 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* bstToGst(TreeNode* root) {
vector<int> valList;
int index = 0;
//2.
recursiveValueListMaker(valList, root);
//3.
for (int i = 1; i < valList.size(); ++i) {
valList[i] += valList[i - 1];
}
//4.
recursiveTreeChanger(valList, root, index);
return root;
}
private:
void recursiveValueListMaker(vector<int>& valList, TreeNode* node) {
if (node->right != 0)
recursiveValueListMaker(valList, node->right);
valList.push_back(node->val);
if (node->left != 0)
recursiveValueListMaker(valList, node->left);
}
void recursiveTreeChanger(vector<int>& valList, TreeNode* node, int& index) {
if (node->right != 0)
recursiveTreeChanger(valList, node->right, index);
node->val = valList[index++];
if (node->left != 0)
recursiveTreeChanger(valList, node->left, index);
}
};
