Leetcode-538- convert binary search tree to cumulative tree

# LeetCode-538- Convert binary search tree to accumulation tree

Given a binary search tree （Binary Search Tree）, Turn it into an accumulation tree （Greater Tree), So that the value of each node is the sum of the original node value plus all nodes greater than it .

Example 1：

 Input :  Original binary search tree :
              5
            /   \
           2     13

 Output :  Convert to an accumulation tree :
             18
            /   \
          20     13

Copy

# Their thinking

Method 1、 recursive ：

Binary search tree is , When the root node in the tree is not empty , The value of all nodes on its left subtree is less than that of its root node . If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of its root node .

According to this characteristic , The cumulative tree can be obtained by traversing in reverse middle order , That is, traverse the right root and the left root first , At the same time, the node values are accumulated , Meet the definition when the value of a node is accumulated by all node values greater than it .

When root Isn't empty , Right subtree recursion , And accumulate node values , Then left subtree recursion , Finally back to root node

Method 2、 iteration ：

Use one Stack To store nodes , Use the middle order traversal of reverse order to accumulate node values , The implementation method is similar to the iterative method of middle order traversal .

# Java Code 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root!=null){
            convertBST(root.right);
            sum+= root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Copy

# Java Code 2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while(temp!=null||!stack.isEmpty()){
            while(temp!=null){
                stack.push(temp);
                temp = temp.right;
            }
            temp = stack.pop();
            sum +=temp.val;
            temp.val = sum;
            temp = temp.left;
        }
        return root;
    }
}

Copy