current position：Home>Sword finger offer II 054 Sum of all values greater than or equal to nodes ｜ 538 ｜ 1038 (Java / C / C + + / Python / go / trust)
Sword finger offer II 054 Sum of all values greater than or equal to nodes ｜ 538 ｜ 1038 (Java / C / C + + / Python / go / trust)
20220131 04:30:35 【White hat of the second leader】
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 thumbsup 】【 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^{4} Between .
 The value of each node is between 10^{4} and 10^{4} 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://leetcodecn.com/problems/w6cpku/
Original title transmission gate ：https://leetcodecn.com/problems/convertbsttogreatertree/
Original title transmission gate ：https://leetcodecn.com/problems/binarysearchtreetogreatersumtree/
copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201310430342006.html
The sidebar is recommended
 [Python from introduction to mastery] (V) Python's builtin data types  sequences and strings. They have no girlfriend, not a nanny, and can only be used as dry goods
 Does Python have a, = operator?
 Go through the string common sense in Python
 Fanwai 4 Handling of mouse events and solutions to common problems in Python opencv
 Summary of common functions for processing strings in Python
 When writing Python scripts, be sure to add this
 Python web crawler  Fundamentals (1)
 Pandas handles duplicate values
 Python notes (23): regular module
 Python crawlers are slow? Concurrent programming to understand it
guess what you like

Parameter passing of Python function

Stroke tuple in Python

Talk about ordinary functions and higherorder functions in Python

[Python data acquisition] page image crawling and saving

[Python data collection] selenium automated test framework

Talk about function passing and other supplements in Python

Python programming simulation poker game

leetcode 160. Intersection of Two Linked Lists （python）

Python crawler actual combat, requests module, python to grab the beautiful wallpaper of a station

Fanwai 5 Detailed description of slider in Python opencv and solutions to common problems
Random recommended
 My friend's stock suffered a terrible loss. When I was angry, I crawled the latest data of securities with Python
 Python interface automation testing framework  if you want to do well, you must first sharpen its tools
 Python multi thread crawling weather website pictures and saving
 How to convert pandas data to excel file
 Python series tutorials 122
 Python Complete Guide  printing data using pyspark
 Python Complete Guide  tuple conversion array
 Stroke the list in python (top)
 Analysis of Python requests module
 Comments and variables in Python
 New statement match, the new version of Python is finally going to introduce switch case?
 Fanwai 6 Different operations for image details in Python opencv
 Python crawler native code learning (I)
 Python quantitative data warehouse building series 2: Python operation database
 Python code reading (Part 50): taking elements from list intervals
 Pyechart + pandas made word cloud pictures of 19 report documents
 [Python crawler] multithreaded daemon & join() blocking
 Python crawls cat pictures in batches to realize thousand image imaging
 Van * Python  simple crawling of a planet
 Input and output of Python practice
 Django ORM details  fields, attributes, operations
 Python web crawler  crawling cloud music review (3)
 Stroke list in python (bottom)
 What cat is the most popular? Python crawls the whole network of cat pictures. Which one is your favorite
 [algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)
 Python shows the progress of downloading files from requests
 Solve the problem that Django celery beat prompts that the database is incorrectly configured and does not support multiple databases
 Bamboolib: this will be one of the most useful Python libraries you've ever seen
 Python quantitative data warehouse construction 3: data drop library code encapsulation
 The source code and implementation of Django CSRF Middleware
 Python hashlib module
 The cover of Python 3 web crawler development (Second Edition) has been determined!
 The introduction method of executing Python source code or Python source code file (novice, please enter the old bird and turn left)
 [Python basics] explain Python basic functions in detail, including teaching and learning
 Python web crawler  crawling cloud music review (4)
 The first step of scientific research: create Python virtual environment on Linux server
 Writing nmap scanning tool in Python  multithreaded version
 leetcode 2057. Smallest Index With Equal Value（python）
 Bamboolib: this will be one of the most useful Python libraries you've ever seen
 Python crawler actual combat, requests module, python realizes capturing a video barrage