Convert binary search tree into cumulative tree (reverse middle order traversal)

538. Convert binary search tree to accumulation tree

difficulty ： secondary

Give a binary Search for Root node of tree , The node values of the tree are different , Please convert it to an accumulation tree （Greater Sum Tree）, Make each node node The new value of is equal to or greater than in the original tree node.val The sum of the values of .

As a reminder , The binary search tree satisfies the following constraints ：

• The left subtree of a node contains only the key Less than Node key node .
• The right subtree of a node contains only the key Greater than Node key node .
• Left and right subtrees must also be binary search trees .

** Be careful ：** This topic and 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ identical

Ideas

I began to see that this problem was also a little confused , Thought of using middle order traversal , But it has never been possible to calculate , Took a look at the official solution , Referred to the Reverse middle order traversal , Well, I fixed my mind

If it is a positive mid order traversal , Then we traverse the elements from small to large

If it is reverse middle order traversal , Then our traversal order is from big to small

At this time, set a variable to count the current sum , When traversing an element , Add its value to sum in , And then sum Copy to node.val, Then go through the next element

package cn.edu.xjtu.carlWay.tree.BST2GreaterTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 538.  Convert binary search tree to accumulation tree  *  Give a binary   Search for   Root node of tree , The node values of the tree are different , Please convert it to an accumulation tree （Greater Sum Tree）, Make each node  node  The new value of is equal to or greater than in the original tree  node.val  The sum of the values of . * <p> *  As a reminder , The binary search tree satisfies the following constraints ： * <p> *  The left subtree of a node contains only the key   Less than   Node key node . *  The right subtree of a node contains only the key   Greater than   Node key node . *  Left and right subtrees must also be binary search trees . *  Be careful ： This topic and  1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/  identical  * <p> * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ */
public class Solution {
    
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
    
        if (root == null) {
    
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}