【Leetcode】1038. Binary Search Tree to Greater Sum Tree（二叉树求和）

雨点打透心脏的1/2处 2022-02-05 08:43 181阅读 0赞

Given the root of a binary **search** tree with distinct values, modify it so that every `node` has a new value equal to the sum of the values of the original tree that are greater than or equal to `node.val`.

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.

**Example 1:**

**![tree.png][]**

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
    Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

**Note:**

1.  The number of nodes in the tree is between `1` and `100`.
2.  Each node will have value between `0` and `100`.
3.  The given tree is a binary search tree.

题目大意：

给出二叉搜索树，按照后序的方式求出每个节点的和。即从右下角的叶子节点开始。

解题思路：

前序遍历得到每个叶子节点的值，保存在vector中，从后到前累加即可。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        int cor_nums;
        vector<TreeNode*> c;
        void helper(TreeNode* root){
            if(root->left==NULL&&root->right==NULL){
                c.push_back(root);
                return;
            }
            if(root->left){
                helper(root->left);
            }
            c.push_back(root);
            if(root->right){
                helper(root->right);
            }
        }
    public:
        TreeNode* bstToGst(TreeNode* root) {
            cor_nums = 0;
            helper(root);
            for(int i = c.size()-2;i>=0;i--){
                c[i]->val += c[i+1]->val;
            }
            return root;    
        }
    };

[tree.png]: https://assets.leetcode.com/uploads/2019/05/02/tree.png