Problem
题目大意:把二叉搜索树的每个节点加上比他大的节点的和。
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
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: reversed inorder traversal
in a BST, we can visit every node in the decreasing order. Using a member sum to track the sum of all visited nodes.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 56 ms class Solution { public: TreeNode* convertBST(TreeNode* root) { sum = 0; inorder(root); return root; } private: int sum; void rinorder(TreeNode* root) { if (root == nullptr) return; rinorder(root->right); root->val = (sum += root->val); rinorder(root->left); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment