[系列文章] leetcode每日一题1038

发布于 17 天前  52 次阅读


1038. Binary Search Tree to Greater Sum Tree

Description

Given the root of 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.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Solution

根据二叉搜索树的特点,一个节点的右孩子的值均大于该节点,若该节点不是根节点,且它是它的父节点的左孩子,则父节点的值也大于该节点的值。使用后序遍历,依次将累加和加到当前节点即可。

Code

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        stack<TreeNode*> nodes;
        TreeNode* head = root;
        int sum = 0;
        while (!nodes.empty() || root) {
            while (root) {
                nodes.push(root);
                root = root->right;
            }
            root = nodes.top();
            nodes.pop();
            root->val += sum;
            sum = root->val;
            root = root->left;
        }
        return head;
    }
};

一只在互联网躬耕的菜鸟,写代码是热爱,二次元也是,mikoto也是