This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
Thank you very much for reading this article ~ welcome 【👍 like 】【⭐ collect 】【📝 comment 】~ Give up is easy, but insist must be cool ~ HOPE we can all make a little progress every day ~ Original ~ https://juejin.cn/user/2771185768884824/posts blog
Index Offer II 054. Sum of all values greater than or equal to nodes | 538. Convert binary search tree to summation tree | 1038.
Given a binary search tree, replace the value of each node with the sum of all nodes in the tree whose value is greater than or equal to that node’s value.
As a reminder, binary search trees satisfy the following constraints:
- The left subtree of a node contains only nodes whose keys are smaller than the node’s keys.
- The right subtree of a node contains only nodes whose keys are greater than the node’s keys.
- The left and right subtrees must also be binary search trees.
Sample 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 the codeThe sample 2
Input: root = [0, NULL,1]Copy the codeSample 3
Input: root = [1,0,2]Copy the codeThe sample of 4
Input: root = [3,2,4,1]Copy the codeprompt
- The number of nodes in the tree is between 0 and 104.
- Each node has a value between -104 and 104.
- All the values in the tree are different.
- The given tree is a binary search tree.
Analysis of the
- This algorithm needs to be translated to make it easier to understand.
- Binary trees, which you’re probably familiar with, are usually forward-order traversal, middle-order traversal, post-order traversal, and then you do some simple logic along the way.
- Binary search trees are a special kind of binary tree, as explained.
- Since the value of each node is replaced by the sum of the values of all nodes in the tree greater than or equal to the value of this node, according to the characteristics of a binary search tree, it is actually to replace the value of each node with its own value and add the sum of the values of the right subtree.
- First of all, each node needs to be traversed, but the order is the key. You will find that normal traversal, middle traversal, and post traversal are not smooth.
- According to the question, is clearly the best order to traverse the right subtree, then the root node, and then the left subtree is the most smoothly, so only need one variable accumulative node value unceasingly, traverse all the nodes to which node is accumulation which values, then assigned to the node, it is just and in sequence traversal is anyway, also is in the reverse sequence traversal.
- Traversing the dolls structure, generally is recursive or cycle (using the stack data structure), recursion is relatively simple, but restricted by the call stack, circulation is stack such data structure was used to simulate the call stack, essentially the same, but number of calls can be more, because of the call stack space is generally limited, a much bigger than the heap space, But the logic of doing the same thing is a little more complicated.
- No matter use recursion to do is to use the stack data structure cycle, all need to tree structure corresponds to the extra memory space, there is a very clever traversal methods is called Morris traversal, non-recursive traversal of the space complexity can be reduced to O (1), the specific implementation of the master has added a detailed annotation, you can also go to wikipedia, do in-depth understanding.
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 older than he is
// It's your turn to handle yourself
sum += cur.val;
cur.val = sum;
// I have already traversed myself, so I should traverse the smaller one
cur = cur.left;
} else {
// The furthest left of the right child, the youngest child older than oneself
// It is the last node in front of itself to be traversed, and the next node should be itself
TreeNode leftmostOfRight = cur.right;
while(leftmostOfRight.left ! =null&& leftmostOfRight.left ! = cur) { leftmostOfRight = leftmostOfRight.left; }if (leftmostOfRight.left == null) {
// No association is made, indicating that the current node is associated for the first time, so as to ensure that the smallest node is traversed after the turn of their own
leftmostOfRight.left = cur;
cur = cur.right;
} else {
// The second iteration is completed, indicating that all the older ones are completed
// Restore the tree structure
leftmostOfRight.left = null;
// It's your turn to handle yourself
sum += cur.val;
cur.val = sum;
// I have already traversed myself, so I should traverse the smaller onecur = cur.left; }}}returnroot; }}Copy the codec
struct TreeNode* convertBST(struct TreeNode* root){
int sum = 0;
struct TreeNode *cur = root;
while(cur ! =NULL) {
if (cur->right == NULL) {
// No child is older than he is
// It's your turn to handle yourself
sum += cur->val;
cur->val = sum;
// I have already traversed myself, so I should traverse the smaller one
cur = cur->left;
} else {
// The furthest left of the right child, the youngest child older than oneself
// It is the last node in front of itself to be traversed, and the next node should be itself
struct TreeNode *leftmostOfRight = cur->right;
while(leftmostOfRight->left ! =NULL&& leftmostOfRight->left ! = cur) { leftmostOfRight = leftmostOfRight->left; }if (leftmostOfRight->left == NULL) {
// No association is made, indicating that the current node is associated for the first time, so as to ensure that the smallest node is traversed after the turn of their own
leftmostOfRight->left = cur;
cur = cur->right;
} else {
// The second iteration is completed, indicating that all the older ones are completed
// Restore the tree structure
leftmostOfRight->left = NULL;
// It's your turn to handle yourself
sum += cur->val;
cur->val = sum;
// I have already traversed myself, so I should traverse the smaller onecur = cur->left; }}}return root;
}
Copy the codec++
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int sum = 0;
TreeNode *cur = root;
while(cur ! =nullptr) {
if (cur->right == nullptr) {
// No child is older than he is
// It's your turn to handle yourself
sum += cur->val;
cur->val = sum;
// I have already traversed myself, so I should traverse the smaller one
cur = cur->left;
} else {
// The furthest left of the right child, the youngest child older than oneself
// It is the last node in front of itself to be traversed, and the next node should be itself
TreeNode *leftmostOfRight = cur->right;
while(leftmostOfRight->left ! =nullptr&& leftmostOfRight->left ! = cur) { leftmostOfRight = leftmostOfRight->left; }if (leftmostOfRight->left == nullptr) {
// No association is made, indicating that the current node is associated for the first time, so as to ensure that the smallest node is traversed after the turn of their own
leftmostOfRight->left = cur;
cur = cur->right;
} else {
// The second iteration is completed, indicating that all the older ones are completed
// Restore the tree structure
leftmostOfRight->left = nullptr;
// It's your turn to handle yourself
sum += cur->val;
cur->val = sum;
// I have already traversed myself, so I should traverse the smaller onecur = cur->left; }}}returnroot; }};Copy the codepython
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
total = 0
cur = root
while cur:
if not cur.right:
# No child is older than he is
# It's your turn to deal with yourself
total += cur.val
cur.val = total
# I have traversed myself, so I should traverse the smaller ones
cur = cur.left
else:
# Leftmost of the right child, the youngest child older than oneself
# is the last node to be traversed before you, and you should be next
leftmostOfRight = cur.right
while leftmostOfRight.left andleftmostOfRight.left ! = cur: leftmostOfRight = leftmostOfRight.leftif not leftmostOfRight.left:
If you go to this node for the first time, associate the current node to ensure that you can get your turn after traversing the smallest node larger than yourself
leftmostOfRight.left = cur
cur = cur.right
else:
# the second time I have traversed this area, it means I have traversed all the ones bigger than myself
Remove the relationship and restore the tree structure
leftmostOfRight.left = None
# It's your turn to deal with yourself
total += cur.val
cur.val = total
# I have traversed myself, so I should traverse the smaller ones
cur = cur.left
return root
Copy the codego
func convertBST(root *TreeNode) *TreeNode {
sum := 0
cur := root
forcur ! =nil {
if cur.Right == nil {
// No child is older than he is
// It's your turn to handle yourself
sum += cur.Val
cur.Val = sum
// I have already traversed myself, so I should traverse the smaller one
cur = cur.Left
} else {
// The furthest left of the right child, the youngest child older than oneself
// It is the last node in front of itself to be traversed, and the next node should be itself
leftmostOfRight := cur.Right
forleftmostOfRight.Left ! =nil&& leftmostOfRight.Left ! = cur { leftmostOfRight = leftmostOfRight.Left }if leftmostOfRight.Left == nil {
// No association is made, indicating that the current node is associated for the first time, so as to ensure that the smallest node is traversed after the turn of their own
leftmostOfRight.Left = cur
cur = cur.Right
} else {
// The second iteration is completed, indicating that all the older ones are completed
// Restore the tree structure
leftmostOfRight.Left = nil
// It's your turn to handle yourself
sum += cur.Val
cur.Val = sum
// I have already traversed myself, so I should traverse the smaller one
cur = cur.Left
}
}
}
return root
}
Copy the coderust
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 older than he is
// It's your turn to handle yourself
sum += cur.as_ref().unwrap().borrow().val;
cur.as_ref().unwrap().borrow_mut().val = sum;
// I have already traversed myself, so I should traverse the smaller one
cur = cur.unwrap().borrow().left.clone();
} else {
// The furthest left of the right child, the youngest child older than oneself
// It is the last node in front of itself to be traversed, and the next node should be itself
let mut leftmostOfRight = cur.as_ref().unwrap().borrow().right.clone();
whileleftmostOfRight.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 association is made, indicating that the current node is associated for the first time, so as to ensure that the smallest node is traversed after the turn of their own
leftmostOfRight.unwrap().borrow_mut().left = cur.clone();
cur = cur.unwrap().borrow().right.clone();
} else {
// The second iteration is completed, indicating that all the older ones are completed
// Restore the tree structure
leftmostOfRight.unwrap().borrow_mut().left = Option: :None;
// It's your turn to handle yourself
sum += cur.as_ref().unwrap().borrow().val;
cur.as_ref().unwrap().borrow_mut().val = sum;
// I have already traversed myself, so I should traverse the smaller one
cur = cur.unwrap().borrow().left.clone();
}
}
}
root
}
}
Copy the code