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)
2022-01-31 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 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 .
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/
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 built-in 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 higher-order 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