给定一个BST，任务是求O（1）空间中大于或等于第K大元素的所有元素之和。 例如：
null
Input : K = 3 8 / 7 10 / / 2 9 13Output : 32Explanation: 3rd largest element is 9 so sum of all elements greater than or equal to 9 are 9 + 10 + 13 = 32.Input : K = 2 8 / 5 11 / 2 7 3Output : 19Explanation: 2nd largest element is 8 so sum of all elements greater than or equal to 8 are 8 + 11 = 19.
方法： 这里的方法是按顺序进行反向遍历，同时只需记录访问的节点数。在访问的节点数小于等于K之前，继续添加当前节点的数据。请使用这样一个事实：BST的反向顺序遍历会给我们一个按降序排序的列表。但是递归或基于堆栈/队列的方法可以进行逆序遍历，因为这两种技术都会消耗大量资源 O（n） 额外的内存，而不是利用 逆莫里斯遍历 进行有序树遍历，这是一种基于 线程二叉树。 下面给出的是 算法：
1) Initialize Current as root.2) Initialize a "count" and "sum" variable to 0.3) While current is not NULL : 3.1) If the current has no right child a) Increment count and check if count is less than or equal to K. 1) Simply add the current node's data in "sum" variable. b) Otherwise, Move to the left child of current. 3.2) Else, here we have 2 cases: a) Find the inorder successor of current Node. Inorder successor is the left most Node in the right subtree or right child itself. b) If the left child of the inorder successor is NULL: 1) Set current as the left child of its inorder successor. 2) Move current Node to its right child. c) Else, if the threaded link between the current Node and it's inorder successor already exists : 1) Set left pointer of the inorder successor as NULL. 2) Increment count and check if the count is less than or equal to K. 2.a) Simply add the current node's data in "sum" variable. 3) Otherwise, Move current to it's left child.4)After the traversal is complete simply return the sum.
以下是上述方法的实施情况：
C++
// C++ program to find sum of // K largest elements in BST using // Reverse Morris Traversal #include <bits/stdc++.h> using namespace std; struct node { int data; struct node *left, *right; }; // Add a new node node* newNode( int item) { node* temp = new node; temp->data = item; temp->left = temp->right = NULL; return temp; } // Function to find the sum of the K largest elements // space efficient method used int SumKLargestUsingReverseMorrisTraversal(node* root, int k) { node* curr = root; int sum = 0; int count = 0; // while doing reverse inorder traversal // keep track of visited nodes while (curr) { if (curr->right == NULL) { // till count is less than k if (++count <= k) { sum += curr->data; } curr = curr->left; } else { // finding the inorder successor node // inorder successor is the left most in right subtree node* succ = curr->right; while (succ->left && succ->left != curr) succ = succ->left; if (succ->left == NULL) { succ->left = curr; curr = curr->right; } // if the threaded link already exists then simply // revert back the tree to original form. else { succ->left = NULL; if (++count <= k) sum += curr->data; curr = curr->left; } } } return sum; } // Driver Code int main() { /* Constructed binary tree is 8 / 7 10 / / 2 9 13 */ struct node* root = newNode(8); root->right = newNode(10); root->left = newNode(7); root->left->left = newNode(2); root->right->left = newNode(9); root->right->right = newNode(13); cout << SumKLargestUsingReverseMorrisTraversal(root, 3); return 0; } |
JAVA
// Java program to find sum of // K largest elements in BST using // Reverse Morris Traversal class GFG { static class node { int data; node left, right; }; // Add a new node static node newNode( int item) { node temp = new node(); temp.data = item; temp.left = temp.right = null ; return temp; } // Function to find the sum of the K largest elements // space efficient method used static int SumKLargestUsingReverseMorrisTraversal(node root, int k) { node curr = root; int sum = 0 ; int count = 0 ; // while doing reverse inorder traversal // keep track of visited nodes while (curr != null ) { if (curr.right == null ) { // till count is less than k if (++count <= k) { sum += curr.data; } curr = curr.left; } else { // finding the inorder successor node // inorder successor is the left most in right subtree node succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null ) { succ.left = curr; curr = curr.right; } // if the threaded link already exists then simply // revert back the tree to original form. else { succ.left = null ; if (++count <= k) sum += curr.data; curr = curr.left; } } } return sum; } // Driver Code public static void main(String[] args) { /* Constructed binary tree is 8 / 7 10 / / 2 9 13 */ node root = newNode( 8 ); root.right = newNode( 10 ); root.left = newNode( 7 ); root.left.left = newNode( 2 ); root.right.left = newNode( 9 ); root.right.right = newNode( 13 ); System.out.println(SumKLargestUsingReverseMorrisTraversal(root, 3 )); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find sum of # K largest elements in BST using # Reverse Morris Traversal class node: def __init__( self , data): self .data = data self .left = None self .right = None # Add a new node def newNode(item): temp = node(item) return temp # Function to find the sum of # the K largest elements # space efficient method used def SumKLargestUsingReverseMorrisTraversal(root, k): curr = root sum = 0 count = 0 # while doing reverse inorder traversal # keep track of visited nodes while (curr): if (curr.right = = None ): # till count is less than k count + = 1 if (count < = k): sum + = curr.data curr = curr.left else : # finding the inorder successor node # inorder successor is the left most # in right subtree succ = curr.right while (succ.left and succ.left ! = curr): succ = succ.left if (succ.left = = None ): succ.left = curr curr = curr.right # if the threaded link already exists # then simply revert back the tree to # original form. else : succ.left = None count + = 1 if (count < = k): sum + = curr.data curr = curr.left return sum # Driver code if __name__ = = "__main__" : ''' Constructed binary tree is 8 / 7 10 / / 2 9 13 ''' root = newNode( 8 ) root.right = newNode( 10 ) root.left = newNode( 7 ) root.left.left = newNode( 2 ) root.right.left = newNode( 9 ) root.right.right = newNode( 13 ) print (SumKLargestUsingReverseMorrisTraversal(root, 3 )) # This code is contributed by Rutvik_56 |
C#
// C# program to find sum of // K largest elements in BST using // Reverse Morris Traversal using System; class GFG { public class node { public int data; public node left, right; }; // Add a new node static node newNode( int item) { node temp = new node(); temp.data = item; temp.left = temp.right = null ; return temp; } // Function to find the sum of the K largest elements // space efficient method used static int SumKLargestUsingReverseMorrisTraversal(node root, int k) { node curr = root; int sum = 0; int count = 0; // while doing reverse inorder traversal // keep track of visited nodes while (curr != null ) { if (curr.right == null ) { // till count is less than k if (++count <= k) { sum += curr.data; } curr = curr.left; } else { // finding the inorder successor node // inorder successor is the left most in right subtree node succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null ) { succ.left = curr; curr = curr.right; } // if the threaded link already exists then simply // revert back the tree to original form. else { succ.left = null ; if (++count <= k) sum += curr.data; curr = curr.left; } } } return sum; } // Driver Code public static void Main(String[] args) { /* Constructed binary tree is 8 / 7 10 / / 2 9 13 */ node root = newNode(8); root.right = newNode(10); root.left = newNode(7); root.left.left = newNode(2); root.right.left = newNode(9); root.right.right = newNode(13); Console.WriteLine(SumKLargestUsingReverseMorrisTraversal(root, 3)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find sum of // K largest elements in BST using // Reverse Morris Traversal class node { constructor() { this .data = 0; this .left = this .right = null ; } } // Add a new node function newNode(item) { let temp = new node(); temp.data = item; temp.left = temp.right = null ; return temp; } // Function to find the sum of the K largest elements // space efficient method used function SumKLargestUsingReverseMorrisTraversal(root,k) { let curr = root; let sum = 0; let count = 0; // while doing reverse inorder traversal // keep track of visited nodes while (curr != null ) { if (curr.right == null ) { // till count is less than k if (++count <= k) { sum += curr.data; } curr = curr.left; } else { // finding the inorder successor node // inorder successor is the left most in right subtree let succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null ) { succ.left = curr; curr = curr.right; } // if the threaded link already exists then simply // revert back the tree to original form. else { succ.left = null ; if (++count <= k) sum += curr.data; curr = curr.left; } } } return sum; } // Driver Code /* Constructed binary tree is 8 / 7 10 / / 2 9 13 */ let root = newNode(8); root.right = newNode(10); root.left = newNode(7); root.left.left = newNode(2); root.right.left = newNode(9); root.right.right = newNode(13); document.write(SumKLargestUsingReverseMorrisTraversal(root, 3)); // This code is contributed by rag2127 </script> |
输出：
32
时间复杂性： O（N） 空间复杂性：O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
