首页 > 代码库 > [LeetCode] Convert BST to Greater Tree
[LeetCode] Convert BST to Greater Tree
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
题目要求将一个BST转换成一个每个节点数值更大的数，要求在全树范围内将比本节点大的所有节点值相加到本节点。由二叉树的中序遍历可知，节点值为：（左） （中） （右）。转换后的树的节点值为：（左 + 中 + 右） （中 + 右） （右）。可以用一个sum值表示每次节点需要相加的值，利用递归传递这个sum。最后完成BST转换。核心是使用逆中序遍历进行遍历生成新的树。
class Solution { public: TreeNode* convertBST(TreeNode* root) { int sum = 0; convertBSTcore(root, sum); return root; } void convertBSTcore(TreeNode* root, int& sum) { if (root == nullptr) return; convertBSTcore(root->right, sum); root->val += sum; sum = root->val; convertBSTcore(root->left, sum); } }; // 36 ms
用迭代完成该过程。
class Solution { public: TreeNode* convertBST(TreeNode* root) { if (root == nullptr) return 0; int sum = 0; stack<TreeNode*> s; TreeNode* node = root; while (node != nullptr || !s.empty()) { while (node != nullptr) { s.push(node); node = node->right; } node = s.top(); s.pop(); node->val += sum; sum = node->val; node = node->left; } return root; } }; // 35 ms
[LeetCode] Convert BST to Greater Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。