48 lines
1.3 KiB
C++
48 lines
1.3 KiB
C++
#include "s0538_convert_bst_to_greater_tree.hpp"
|
|
|
|
// 思路一:直观递归
|
|
TreeNode* S0538::convertBST1(TreeNode* root) {
|
|
// 为空则直接返回
|
|
if (root == nullptr) return nullptr;
|
|
|
|
// 更新右子树
|
|
root->right = convertBST1(root->right);
|
|
|
|
// 更新根节点的值
|
|
if (root->right != nullptr) {
|
|
// 找到右子树的最左侧节点
|
|
TreeNode* node = root->right;
|
|
while (node->left != nullptr) node = node->left;
|
|
// 根节点 = 根节点 + 右子树的最左侧节点
|
|
root->val += node->val;
|
|
}
|
|
|
|
// 接下来处理左子树
|
|
if (root->left != nullptr) {
|
|
// 先把根节点的值加到左子树的最右侧点
|
|
TreeNode* node = root->left;
|
|
// 找到左子树的最右侧点
|
|
while (node->right != nullptr) node = node->right;
|
|
// 加上去
|
|
node->val += root->val;
|
|
// 更新左子树
|
|
root->left = convertBST1(root->left);
|
|
}
|
|
|
|
// 返回
|
|
return root;
|
|
}
|
|
|
|
// 思路二:反序中序遍历
|
|
// 反序中序遍历的遍历路径正好和累加树的路径相同,因此可以直接用它来遍历
|
|
// 用一个全局变量 sum 记录遍历过程中每个节点的值
|
|
TreeNode* S0538::convertBST2(TreeNode* root) {
|
|
if (root != nullptr) {
|
|
convertBST2(root->right);
|
|
sum += root->val;
|
|
root->val = sum;
|
|
convertBST2(root->left);
|
|
}
|
|
return root;
|
|
}
|