#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;
}