LeetCode 剑指 Offer II 054. 所有大于等于节点的值之和

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

示例 1：
在这里插入图片描述
输入：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值互不相同。
给定的树为二叉搜索树。

解法一：反向中序遍历树，每遍历到一个节点，将其加到所有节点和中，然后将该节点值设为当前所有节点和：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);

        return root;
    }
private:
    int sum = 0;
};

如果树有n个节点，则此算法时间复杂度为O（n），空间复杂度平均情况下O（lgn），最差情况下为O（n），主要的空间开销是栈开销，当二叉搜索树退化成链表时，空间复杂度达到最大。

解法二：此解法是解法一的迭代版，用一个stack来模拟函数调用栈：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        stack<TreeNode *> s;
        TreeNode *curNode = root;
        while (curNode || !s.empty()) {
            while (curNode) {
                s.push(curNode);
                curNode = curNode->right;
            }

            curNode = s.top();
            s.pop();
            sum += curNode->val;
            curNode->val = sum;

            curNode = curNode->left;
        }

        return root;
    }
private:
    int sum = 0;
};

解法三：Morris遍历，它的反向中序遍历的规则如下：
1.如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；

2.如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；

（1）如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；

（2）如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；

3.重复步骤1和步骤2，直到遍历结束。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        TreeNode *node = root;
        int sum = 0;

        while (node)
        {
            if (node->right == nullptr)
            {
                sum += node->val;
                node->val = sum;
                node = node->left;
            }
            else
            {
                TreeNode *mostLeftOfRight = getMostLeftOfRight(node);
                if (mostLeftOfRight->left == nullptr)
                {
                    mostLeftOfRight->left = node;
                    node = node->right;
                }
                else if (mostLeftOfRight->left == node)
                {
                    sum += node->val;
                    node->val = sum;
                    mostLeftOfRight->left = nullptr;
                    node = node->left;
                }
            }
        }

        return root;
    }

private:
    TreeNode *getMostLeftOfRight(TreeNode *node)
    {
        TreeNode *mostLeftOfRight = node->right;
        while (mostLeftOfRight->left && mostLeftOfRight->left != node)
        {
            mostLeftOfRight = mostLeftOfRight->left;
        }

        return mostLeftOfRight;
    }
};