This is my participation 11 The fourth of the yuegengwen challenge 7 God , Check out the activity details ：2021 One last more challenge

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader ：https://juejin.cn/user/2771185768884824/posts Original blog ~

---

The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes ｜538. Convert binary search tree to accumulation tree ｜1038. Convert binary search tree to accumulation tree ：

Given a binary search tree , Please replace the value of each node with the sum of all node values greater than or equal to the node value in the tree .

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 .

Examples 1

 Input ：
    root = [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]
 Copy code 

Examples 2

 Input ：
    root = [0,null,1]

 Output ：
    [1,null,1]
 Copy code 

Examples 3

 Input ：
    root = [1,0,2]

 Output ：
    [3,3,2]
 Copy code 

Examples 4

 Input ：
        root = [3,2,4,1]
	
 Output ：
        [7,9,4,10]
 Copy code 

Tips

• The number of nodes in the tree is between 0 and 10⁴ Between .
• The value of each node is between -10⁴ and 10⁴ Between .
• All the values in the tree Different from each other .
• The given tree is a binary search tree .

---

analysis

• This algorithm problem needs to be translated , Easy to understand .
• Binary tree , You should be familiar with , Generally, it is positive order ergodic , In the sequence traversal , After the sequence traversal , Then, some simple logic is carried out in the process of traversal .
• Binary search tree is a special binary tree , The title has been explained .
• Because we need to replace the value of each node with the sum of all node values greater than or equal to the node value in the tree , According to the characteristics of binary search tree , In fact, it is to replace the value of each node with its own value and accumulate the sum of the values of the right subtree .
• First of all, you need to traverse each node , But in what order is the key , You will find that regular positive order traversal , In the sequence traversal , The post order traversal is not smooth .
• According to the meaning of the title , Obviously, the best order is to traverse the right subtree first , And then the root node , Then the left sub tree is the smoothest , Only one variable is needed to continuously accumulate node values , The value of which node is accumulated when traversing to which node , Then assign a value to this node , This is exactly the same as the middle order traversal , That is, inverse middle order traversal .
• Traverse this doll structure , It is usually recursion or loop （ Using stack data structure ）, Recursion is relatively simple , But limited by the call stack , In fact, the loop simulates the call stack with a data structure such as stack , Essentially almost , But the number of calls can be more , Because the space of call stack is generally limited , The heap space is much larger , But to achieve the same function , The logic is also more complex .
• Whether recursion or stack data structure is used to cycle , All require additional memory space corresponding to the tree structure , There is a very clever traversal method called Morris Traverse , The space complexity in non recursive traversal can be reduced to O (1), The specific implementation of the second leader has been annotated in detail , You can also go to the encyclopedia , Get to know more about .

---

Answer key

java

class Solution {
    public TreeNode convertBST(TreeNode root) {
        int      sum = 0;
        TreeNode cur = root;

        while (cur != null) {
            if (cur.right == null) {
                //  No child is worth more than himself 
                //  It's your turn to deal with yourself 
                sum += cur.val;
                cur.val = sum;
                //  I'm finished , So you should traverse smaller than yourself 
                cur = cur.left;
            } else {
                //  The far left of the right child , The youngest child older than himself 
                //  That is, the last traversal node in front of you , The next one should be yourself 
                TreeNode leftmostOfRight = cur.right;
                while (leftmostOfRight.left != null
                    && leftmostOfRight.left != cur) {
                    leftmostOfRight = leftmostOfRight.left;
                }
                if (leftmostOfRight.left == null) {
                    //  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                    leftmostOfRight.left = cur;
                    cur = cur.right;
                } else {
                    //  The second traversal comes here , It means that all the older ones have gone through 
                    //  Terminate the relationship , Restore tree structure 
                    leftmostOfRight.left = null;
                    //  It's your turn to deal with yourself 
                    sum += cur.val;
                    cur.val = sum;
                    //  I'm finished , So you should traverse smaller than yourself 
                    cur = cur.left;
                }
            }
        }

        return root;
    }
}
 Copy code 

---

c

struct TreeNode* convertBST(struct TreeNode* root){
    int sum = 0;
    struct TreeNode *cur = root;

    while (cur != NULL) {
        if (cur->right == NULL) {
            //  No child is worth more than himself 
            //  It's your turn to deal with yourself 
            sum += cur->val;
            cur->val = sum;
            //  I'm finished , So you should traverse smaller than yourself 
            cur = cur->left;
        } else {
            //  The far left of the right child , The youngest child older than himself 
            //  That is, the last traversal node in front of you , The next one should be yourself 
            struct TreeNode *leftmostOfRight = cur->right;
            while (leftmostOfRight->left != NULL
                   && leftmostOfRight->left != cur) {
                leftmostOfRight = leftmostOfRight->left;
            }
            if (leftmostOfRight->left == NULL) {
                //  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                leftmostOfRight->left = cur;
                cur = cur->right;
            } else {
                //  The second traversal comes here , It means that all the older ones have gone through 
                //  Terminate the relationship , Restore tree structure 
                leftmostOfRight->left = NULL;
                //  It's your turn to deal with yourself 
                sum += cur->val;
                cur->val = sum;
                //  I'm finished , So you should traverse smaller than yourself 
                cur = cur->left;
            }
        }
    }

    return root;
}
 Copy code 

---

c++

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        TreeNode *cur = root;

        while (cur != nullptr) {
            if (cur->right == nullptr) {
                //  No child is worth more than himself 
                //  It's your turn to deal with yourself 
                sum += cur->val;
                cur->val = sum;
                //  I'm finished , So you should traverse smaller than yourself 
                cur = cur->left;
            } else {
                //  The far left of the right child , The youngest child older than himself 
                //  That is, the last traversal node in front of you , The next one should be yourself 
                TreeNode *leftmostOfRight = cur->right;
                while (leftmostOfRight->left != nullptr
                       && leftmostOfRight->left != cur) {
                    leftmostOfRight = leftmostOfRight->left;
                }
                if (leftmostOfRight->left == nullptr) {
                    //  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                    leftmostOfRight->left = cur;
                    cur = cur->right;
                } else {
                    //  The second traversal comes here , It means that all the older ones have gone through 
                    //  Terminate the relationship , Restore tree structure 
                    leftmostOfRight->left = nullptr;
                    //  It's your turn to deal with yourself 
                    sum += cur->val;
                    cur->val = sum;
                    //  I'm finished , So you should traverse smaller than yourself 
                    cur = cur->left;
                }
            }
        }

        return root;
    }
};
 Copy code 

---

python

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        total = 0
        cur = root

        while cur:
            if not cur.right:
                #  No child is worth more than himself 
                #  It's your turn to deal with yourself 
                total += cur.val
                cur.val = total
                #  I'm finished , So you should traverse smaller than yourself 
                cur = cur.left
            else:
                #  The far left of the right child , The youngest child older than himself 
                #  That is, the last traversal node in front of you , The next one should be yourself 
                leftmostOfRight = cur.right
                while leftmostOfRight.left and leftmostOfRight.left != cur:
                    leftmostOfRight = leftmostOfRight.left

                if not leftmostOfRight.left:
                    #  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                    leftmostOfRight.left = cur
                    cur = cur.right
                else:
                    #  The second traversal comes here , It means that all the older ones have gone through 
                    #  Terminate the relationship , Restore tree structure 
                    leftmostOfRight.left = None
                    #  It's your turn to deal with yourself 
                    total += cur.val
                    cur.val = total
                    #  I'm finished , So you should traverse smaller than yourself 
                    cur = cur.left

        return root
        
 Copy code 

---

go

func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    cur := root

    for cur != nil {
        if cur.Right == nil {
            //  No child is worth more than himself 
            //  It's your turn to deal with yourself 
            sum += cur.Val
            cur.Val = sum
            //  I'm finished , So you should traverse smaller than yourself 
            cur = cur.Left
        } else {
            //  The far left of the right child , The youngest child older than himself 
            //  That is, the last traversal node in front of you , The next one should be yourself 
            leftmostOfRight := cur.Right
            for leftmostOfRight.Left != nil && leftmostOfRight.Left != cur {
                    leftmostOfRight = leftmostOfRight.Left
            }
            if leftmostOfRight.Left == nil {
                //  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                leftmostOfRight.Left = cur
                cur = cur.Right
            } else {
                //  The second traversal comes here , It means that all the older ones have gone through 
                //  Terminate the relationship , Restore tree structure 
                leftmostOfRight.Left = nil
                //  It's your turn to deal with yourself 
                sum += cur.Val
                cur.Val = sum
                //  I'm finished , So you should traverse smaller than yourself 
                cur = cur.Left
            }
        }
    }

    return root
}
 Copy code 

---

rust

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut sum = 0;
        let mut cur = root.clone();

        while cur.is_some() {
            if cur.as_ref().unwrap().borrow().right.is_none() {
                //  No child is worth more than himself 
                //  It's your turn to deal with yourself 
                sum += cur.as_ref().unwrap().borrow().val;
                cur.as_ref().unwrap().borrow_mut().val = sum;
                //  I'm finished , So you should traverse smaller than yourself 
                cur = cur.unwrap().borrow().left.clone();
            } else {
                //  The far left of the right child , The youngest child older than himself 
                //  That is, the last traversal node in front of you , The next one should be yourself 
                let mut leftmostOfRight = cur.as_ref().unwrap().borrow().right.clone();
                while leftmostOfRight.as_ref().unwrap().borrow().left.is_some()
                    && leftmostOfRight.as_ref().unwrap().borrow().left != cur {
                    leftmostOfRight = leftmostOfRight.unwrap().borrow().left.clone();
                }
                if leftmostOfRight.as_ref().unwrap().borrow().left.is_none() {
                    //  No connection has been made , Explain the first time here , Associate the current node , Make sure that it's your turn after traversing the smallest node larger than yourself 
                    leftmostOfRight.unwrap().borrow_mut().left = cur.clone();
                    cur = cur.unwrap().borrow().right.clone();
                } else {
                    //  The second traversal comes here , It means that all the older ones have gone through 
                    //  Terminate the relationship , Restore tree structure 
                    leftmostOfRight.unwrap().borrow_mut().left = Option::None;
                    //  It's your turn to deal with yourself 
                    sum += cur.as_ref().unwrap().borrow().val;
                    cur.as_ref().unwrap().borrow_mut().val = sum;
                    //  I'm finished , So you should traverse smaller than yourself 
                    cur = cur.unwrap().borrow().left.clone();
                }
            }
        }

        root
    }
}
 Copy code 

---

---

Original title transmission gate ：https://leetcode-cn.com/problems/w6cpku/

Original title transmission gate ：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

Original title transmission gate ：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/

---