# Sword finger offer II 054 Sum of all values greater than or equal to nodes ｜ 538 ｜ 1038 (Java / C / C + + / Python / go / trust)

2022-01-31 04:30:35

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 104 Between .
• The value of each node is between -104 and 104 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 .

## 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 `````` 