将二叉搜索树转换为累加树

题目

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

思路

根据二叉搜索树的特性，每个节点需要加上大于自己的值，怎样寻找大于自己的值？

1. 若该节点为父节点的右孩子，只需加上该节点右子树上的所有孩子
2. 若该节点为父节点的左孩子，需要加上该节点右子树上的所有孩子，并且包含父节点和父节点右子树上的所有孩子，若父节点依然为它的父节点的左孩子，那么依次相加。

方法1

根据上述思路，使用递归（右根左），这样

1. 若该节点为父节点的右孩子，只需加上该节点右子树上的第一个孩子的值，因为第一个孩子的值已经是累加后的
2. 若该节点为父节点的左孩子，需要加上该节点右子树上的第一个孩子的值，和父节点的值。

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if(NULL == root) return NULL;

        TreeNode* right = convertBST(root->right);
        if(right) root->val += right->val;
        TreeNode* left = convertBST(root->left);
        if(left) left->val += root->val;

        return root;
    }
};

这样的思路不行，但是我思考了好久好久，有很多细节没有考虑到，如：

1. 递归时，不能让父节点每次都加上它的第一个右孩子，因为它的右孩子可能也有左孩子，左孩子的值比右孩子的值更大
2. 以根节点来说，右子树的遍历和左子树的遍历是不一样的，因为左子树的最右边节点需要加上根节点的值，但是右子树的最右边节点却不用考虑

思路2

遍历所有的节点得到所有节点的和，然后中序遍历，将和赋给第一个节点，然后遍历到哪一个节点，就用和减去上一个节点原有的值为该节点的值，更新和。

class Solution {
public:
    int pre_val = -10000;
    void PreOrder(TreeNode* root, int& sum)
    {
        if(NULL == root) return;
        sum += root->val;
        PreOrder(root->left, sum);
        PreOrder(root->right, sum);
    }
    void ConvertBSTAux(TreeNode* root, int& sum)
    {
        if(NULL == root) return;

        ConvertBSTAux(root->left, sum);
        int tmp = root->val;
        root->val = pre_val == -10000 ? sum : sum - pre_val;
        sum = root->val;
        pre_val = tmp;
        ConvertBSTAux(root->right, sum);
    }
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        PreOrder(root, sum);
        ConvertBSTAux(root, sum);
        return root;
    }
};

思路3

结合思路1和思路2，可以通过右根左遍历树，除了第一个节点（序列中最大的元素）外，每个节点加上前一个节点的元素，因为前面的节点都是比该节点大的

方法1

class Solution {
public:
    TreeNode* pre_node = NULL;
    TreeNode* convertBST(TreeNode* root) {
        if(NULL == root)  return root;

        convertBST(root->right);
        root->val += pre_node == NULL ? 0 : pre_node->val;
        pre_node = root;
        convertBST(root->left);
        return root;
    }
};

方法2

只是pre_node的定义变了，用了更巧妙的定义，代码随想录提供的

class Solution {
private:
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

方法3

迭代法

代码随想录提供的

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   // 右
            } else {
                cur = st.top();     // 中
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    // 左
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};