给定一棵二叉树，求同一垂直线上的节点的垂直和。通过不同的垂直线打印所有总和。
null
例如：
1 / 2 3 / / 4 5 6 7
这棵树有5条垂直线 垂直线1只有一个节点4=>垂直和为4 垂直线2：只有一个节点2=>垂直和为2 垂直线3：有三个节点：1,5,6=>垂直和为1+5+6=12 垂直线4：只有一个节点3=>垂直和为3 垂直线5：只有一个节点7=>垂直和为7 所以预期的产出是4，2，12，3和7
我们讨论过 散列 基于 第一组 .基于哈希的解决方案需要维护哈希表。我们知道，哈希需要的空间比其中的条目数还要大。在这篇帖子里， 双链表 讨论了基于该方法的解决方案。这里讨论的解决方案只需要链表的n个节点，其中n是二叉树中垂直线的总数。下面是算法。
verticalSumDLL(root)1) Create a node of doubly linked list node with value 0. Let the node be llnode.2) verticalSumDLL(root, llnode)verticalSumDLL(tnode, llnode)1) Add current node's data to its vertical line llnode.data = llnode.data + tnode.data;2) Recursively process left subtree // If left child is not empty if (tnode.left != null) { if (llnode.prev == null) { llnode.prev = new LLNode(0); llnode.prev.next = llnode; } verticalSumDLLUtil(tnode.left, llnode.prev); }3) Recursively process right subtree if (tnode.right != null) { if (llnode.next == null) { llnode.next = new LLNode(0); llnode.next.prev = llnode; } verticalSumDLLUtil(tnode.right, llnode.next); }
C++
/// C++ program of space optimized solution /// to find vertical sum of binary tree. #include <bits/stdc++.h> using namespace std; /// Tree node structure struct TNode{ int key; struct TNode *left, *right; }; /// Function to create new tree node TNode* newTNode( int key) { TNode* temp = new TNode; temp->key = key; temp->left = temp->right = NULL; return temp; } /// Doubly linked list structure struct LLNode{ int key; struct LLNode *prev, *next; }; /// Function to create new Linked List Node LLNode* newLLNode( int key) { LLNode* temp = new LLNode; temp->key = key; temp->prev = temp->next = NULL; return temp; } /// Function that creates Linked list and store /// vertical sum in it. void verticalSumDLLUtil(TNode *root, LLNode *sumNode) { /// Update sum of current line by adding value /// of current tree node. sumNode->key = sumNode->key + root->key; /// Recursive call to left subtree. if (root->left) { if (sumNode->prev == NULL) { sumNode->prev = newLLNode(0); sumNode->prev->next = sumNode; } verticalSumDLLUtil(root->left, sumNode->prev); } /// Recursive call to right subtree. if (root->right) { if (sumNode->next == NULL) { sumNode->next = newLLNode(0); sumNode->next->prev = sumNode; } verticalSumDLLUtil(root->right, sumNode->next); } } /// Function to print vertical sum of Tree. /// It uses verticalSumDLLUtil() to calculate sum. void verticalSumDLL(TNode* root) { /// Create Linked list node for /// line passing through root. LLNode* sumNode = newLLNode(0); /// Compute vertical sum of different lines. verticalSumDLLUtil(root, sumNode); /// Make doubly linked list pointer point /// to first node in list. while (sumNode->prev != NULL){ sumNode = sumNode->prev; } /// Print vertical sum of different lines /// of binary tree. while (sumNode != NULL){ cout << sumNode->key << " " ; sumNode = sumNode->next; } } int main() { /* 1 / / 2 3 / / / / 4 5 6 7 */ TNode *root = newTNode(1); root->left = newTNode(2); root->right = newTNode(3); root->left->left = newTNode(4); root->left->right = newTNode(5); root->right->left = newTNode(6); root->right->right = newTNode(7); cout << "Vertical Sums are" ; verticalSumDLL(root); return 0; } // This code is contributed by Rahul Titare |
JAVA
// Java implementation of space optimized solution // to find vertical sum. public class VerticalSumBinaryTree { // Prints vertical sum of different vertical // lines in tree. This method mainly uses // verticalSumDLLUtil(). static void verticalSumDLL(TNode root) { // Create a doubly linked list node to // store sum of lines going through root. // Vertical sum is initialized as 0. LLNode llnode = new LLNode( 0 ); // Compute vertical sum of different lines verticalSumDLLUtil(root, llnode); // llnode refers to sum of vertical line // going through root. Move llnode to the // leftmost line. while (llnode.prev != null ) llnode = llnode.prev; // Prints vertical sum of all lines starting // from leftmost vertical line while (llnode != null ) { System.out.print(llnode.data + " " ); llnode = llnode.next; } } // Constructs linked list static void verticalSumDLLUtil(TNode tnode, LLNode llnode) { // Add current node's data to its vertical line llnode.data = llnode.data + tnode.data; // Recursively process left subtree if (tnode.left != null ) { if (llnode.prev == null ) { llnode.prev = new LLNode( 0 ); llnode.prev.next = llnode; } verticalSumDLLUtil(tnode.left, llnode.prev); } // Process right subtree if (tnode.right != null ) { if (llnode.next == null ) { llnode.next = new LLNode( 0 ); llnode.next.prev = llnode; } verticalSumDLLUtil(tnode.right, llnode.next); } } // Driver code public static void main(String[] args) { // Let us construct the tree shown above TNode root = new TNode( 1 ); root.left = new TNode( 2 ); root.right = new TNode( 3 ); root.left.left = new TNode( 4 ); root.left.right = new TNode( 5 ); root.right.left = new TNode( 6 ); root.right.right = new TNode( 7 ); System.out.println( "Vertical Sums are" ); verticalSumDLL(root); } // Doubly Linked List Node static class LLNode { int data; LLNode prev, next; public LLNode( int d) { data = d; } } // Binary Tree Node static class TNode { int data; TNode left, right; public TNode( int d) { data = d; } } } |
Python3
# Python3 program of space optimized # solution to find vertical sum of # binary tree. # Tree node structure class TNode: def __init__( self , key): self .key = key self .left = None self .right = None # Doubly linked list structure class LLNode: def __init__( self , key): self .key = key self .prev = None self . next = None # Function that creates Linked list and store # vertical sum in it. def verticalSumDLLUtil(root: TNode, sumNode: LLNode) - > None : # Update sum of current line by adding # value of current tree node. sumNode.key = sumNode.key + root.key # Recursive call to left subtree. if (root.left): if (sumNode.prev = = None ): sumNode.prev = LLNode( 0 ) sumNode.prev. next = sumNode verticalSumDLLUtil(root.left, sumNode.prev) # Recursive call to right subtree. if (root.right): if (sumNode. next = = None ): sumNode. next = LLNode( 0 ) sumNode. next .prev = sumNode verticalSumDLLUtil(root.right, sumNode. next ) # Function to print vertical sum of Tree. # It uses verticalSumDLLUtil() to calculate sum. def verticalSumDLL(root: TNode) - > None : # Create Linked list node for # line passing through root. sumNode = LLNode( 0 ) # Compute vertical sum of different lines. verticalSumDLLUtil(root, sumNode) # Make doubly linked list pointer point # to first node in list. while (sumNode.prev ! = None ): sumNode = sumNode.prev # Print vertical sum of different lines # of binary tree. while (sumNode ! = None ): print (sumNode.key, end = " " ) sumNode = sumNode. next # Driver code if __name__ = = "__main__" : ''' 1 / / 2 3 / / / / 4 5 6 7 ''' root = TNode( 1 ) root.left = TNode( 2 ) root.right = TNode( 3 ) root.left.left = TNode( 4 ) root.left.right = TNode( 5 ) root.right.left = TNode( 6 ) root.right.right = TNode( 7 ) print ( "Vertical Sums are" ) verticalSumDLL(root) # This code is contributed by sanjeev2552 |
C#
// C# implementation of space optimized // solution to find vertical sum. using System; class GFG { // Prints vertical sum of different vertical // lines in tree. This method mainly uses // verticalSumDLLUtil(). public static void verticalSumDLL(TNode root) { // Create a doubly linked list node to // store sum of lines going through root. // Vertical sum is initialized as 0. LLNode llnode = new LLNode(0); // Compute vertical sum of different lines verticalSumDLLUtil(root, llnode); // llnode refers to sum of vertical line // going through root. Move llnode to the // leftmost line. while (llnode.prev != null ) { llnode = llnode.prev; } // Prints vertical sum of all lines // starting from leftmost vertical line while (llnode != null ) { Console.Write(llnode.data + " " ); llnode = llnode.next; } } // Constructs linked list public static void verticalSumDLLUtil(TNode tnode, LLNode llnode) { // Add current node's data to // its vertical line llnode.data = llnode.data + tnode.data; // Recursively process left subtree if (tnode.left != null ) { if (llnode.prev == null ) { llnode.prev = new LLNode(0); llnode.prev.next = llnode; } verticalSumDLLUtil(tnode.left, llnode.prev); } // Process right subtree if (tnode.right != null ) { if (llnode.next == null ) { llnode.next = new LLNode(0); llnode.next.prev = llnode; } verticalSumDLLUtil(tnode.right, llnode.next); } } // Doubly Linked List Node public class LLNode { public int data; public LLNode prev, next; public LLNode( int d) { data = d; } } // Binary Tree Node public class TNode { public int data; public TNode left, right; public TNode( int d) { data = d; } } // Driver code public static void Main( string [] args) { // Let us construct the tree shown above TNode root = new TNode(1); root.left = new TNode(2); root.right = new TNode(3); root.left.left = new TNode(4); root.left.right = new TNode(5); root.right.left = new TNode(6); root.right.right = new TNode(7); Console.WriteLine( "Vertical Sums are" ); verticalSumDLL(root); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript implementation of space optimized // solution to find vertical sum. // Prints vertical sum of different vertical // lines in tree. This method mainly uses // verticalSumDLLUtil(). function verticalSumDLL(root) { // Create a doubly linked list node to // store sum of lines going through root. // Vertical sum is initialized as 0. var llnode = new LLNode(0); // Compute vertical sum of different lines verticalSumDLLUtil(root, llnode); // llnode refers to sum of vertical line // going through root. Move llnode to the // leftmost line. while (llnode.prev != null ) { llnode = llnode.prev; } // Prints vertical sum of all lines // starting from leftmost vertical line while (llnode != null ) { document.write(llnode.data + " " ); llnode = llnode.next; } } // Constructs linked list function verticalSumDLLUtil(tnode, llnode) { // Add current node's data to // its vertical line llnode.data = llnode.data + tnode.data; // Recursively process left subtree if (tnode.left != null ) { if (llnode.prev == null ) { llnode.prev = new LLNode(0); llnode.prev.next = llnode; } verticalSumDLLUtil(tnode.left, llnode.prev); } // Process right subtree if (tnode.right != null ) { if (llnode.next == null ) { llnode.next = new LLNode(0); llnode.next.prev = llnode; } verticalSumDLLUtil(tnode.right, llnode.next); } } // Doubly Linked List Node class LLNode { constructor(d) { this .data = d; this .prev = null ; this .next = null ; } } // Binary Tree Node class TNode { constructor(d) { this .data = d; this .left = null ; this .right = null ; } } // Driver code // Let us construct the tree shown above var root = new TNode(1); root.left = new TNode(2); root.right = new TNode(3); root.left.left = new TNode(4); root.left.right = new TNode(5); root.right.left = new TNode(6); root.right.right = new TNode(7); document.write( "Vertical Sums are<br>" ); verticalSumDLL(root); // This code is contributed by itsok </script> |
输出：
Vertical Sums are4 2 12 3 7
本文由 拉胡尔·蒂塔雷 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
