给定一棵二叉树，求同一垂直线上的节点的垂直和。通过不同的垂直线打印所有总和。 例如：
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
我们需要检查所有节点与根的水平距离。如果两个节点具有相同的水平距离（HD），则它们位于同一条垂直线上。高清的想法很简单。根的HD为0，右边缘（连接到右子树的边缘）视为+1水平距离，左边缘视为-1水平距离。例如，在上面的树中，节点4的HD为-2，节点2的HD为-1，节点5和6的HD为0，节点7的HD为+2。 我们可以按顺序遍历给定的二叉树。在遍历树时，我们可以递归地计算HDs。我们最初将水平距离传递为0表示根。对于左子树，我们将水平距离传递为根的水平距离减1。对于右子树，我们将水平距离传递为根的水平距离加1。 下面是同样的Java实现。HashMap用于存储不同水平距离的垂直和。感谢Nages推荐这种方法。
C++
// C++ program to find Vertical Sum in // a given Binary Tree #include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *left, *right; }; // A utility function to create a new // Binary Tree node Node* newNode( int data) { Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Traverses the tree in in-order form and // populates a hashMap that contains the // vertical sum void verticalSumUtil(Node *node, int hd, map< int , int > &Map) { // Base case if (node == NULL) return ; // Recur for left subtree verticalSumUtil(node->left, hd-1, Map); // Add val of current node to // map entry of corresponding hd Map[hd] += node->data; // Recur for right subtree verticalSumUtil(node->right, hd+1, Map); } // Function to find vertical sum void verticalSum(Node *root) { // a map to store sum of nodes for each // horizontal distance map < int , int > Map; map < int , int > :: iterator it; // populate the map verticalSumUtil(root, 0, Map); // Prints the values stored by VerticalSumUtil() for (it = Map.begin(); it != Map.end(); ++it) { cout << it->first << ": " << it->second << endl; } } // Driver program to test above functions int main() { // Create binary tree as shown in above figure Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); root->right->right->right = newNode(9); cout << "Following are the values of vertical" " sums with the positions of the " "columns with respect to root" ; verticalSum(root); return 0; } // This code is contributed by Aditi Sharma |
JAVA
import java.util.TreeMap; // Class for a tree node class TreeNode { // data members private int key; private TreeNode left; private TreeNode right; // Accessor methods public int key() { return key; } public TreeNode left() { return left; } public TreeNode right() { return right; } // Constructor public TreeNode( int key) { this .key = key; left = null ; right = null ; } // Methods to set left and right subtrees public void setLeft(TreeNode left) { this .left = left; } public void setRight(TreeNode right) { this .right = right; } } // Class for a Binary Tree class Tree { private TreeNode root; // Constructors public Tree() { root = null ; } public Tree(TreeNode n) { root = n; } // Method to be called by the consumer classes // like Main class public void VerticalSumMain() { VerticalSum(root); } // A wrapper over VerticalSumUtil() private void VerticalSum(TreeNode root) { // base case if (root == null ) { return ; } // Creates an empty TreeMap hM TreeMap<Integer, Integer> hM = new TreeMap<Integer, Integer>(); // Calls the VerticalSumUtil() to store the // vertical sum values in hM VerticalSumUtil(root, 0 , hM); // Prints the values stored by VerticalSumUtil() if (hM != null ) { System.out.println(hM.entrySet()); } } // Traverses the tree in in-order form and builds // a hashMap hM that contains the vertical sum private void VerticalSumUtil(TreeNode root, int hD, TreeMap<Integer, Integer> hM) { // base case if (root == null ) { return ; } // Store the values in hM for left subtree VerticalSumUtil(root.left(), hD - 1 , hM); // Update vertical sum for hD of this node int prevSum = (hM.get(hD) == null ) ? 0 : hM.get(hD); hM.put(hD, prevSum + root.key()); // Store the values in hM for right subtree VerticalSumUtil(root.right(), hD + 1 , hM); } } // Driver class to test the verticalSum methods public class Main { public static void main(String[] args) { /* Create the following Binary Tree 1 / 2 3 / / 4 5 6 7 */ TreeNode root = new TreeNode( 1 ); root.setLeft( new TreeNode( 2 )); root.setRight( new TreeNode( 3 )); root.left().setLeft( new TreeNode( 4 )); root.left().setRight( new TreeNode( 5 )); root.right().setLeft( new TreeNode( 6 )); root.right().setRight( new TreeNode( 7 )); Tree t = new Tree(root); System.out.println( "Following are the values of" + " vertical sums with the positions" + " of the columns with respect to root " ); t.VerticalSumMain(); } } |
Python3
# Python3 program to find Vertical Sum in # a given Binary Tree # Node definition class newNode: def __init__( self , data): self .left = None self .right = None self .data = data # Traverses the tree in in-order form and # populates a hashMap that contains the # vertical sum def verticalSumUtil(root, hd, Map ): # Base case if (root = = None ): return # Recur for left subtree verticalSumUtil(root.left, hd - 1 , Map ) # Add val of current node to # map entry of corresponding hd if (hd in Map .keys()): Map [hd] = Map [hd] + root.data else : Map [hd] = root.data # Recur for right subtree verticalSumUtil(root.right, hd + 1 , Map ) # Function to find vertical_sum def verticalSum(root): # a dictionary to store sum of # nodes for each horizontal distance Map = {} # Populate the dictionary verticalSumUtil(root, 0 , Map ); # Prints the values stored # by VerticalSumUtil() for i,j in Map .items(): print (i, "=" , j, end = ", " ) # Driver Code if __name__ = = "__main__" : ''' Create the following Binary Tree 1 / 2 3 / / 4 5 6 7 ''' root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.right.left = newNode( 6 ) root.right.right = newNode( 7 ) print ( "Following are the values of vertical " "sums with the positions of the " "columns with respect to root" ) verticalSum(root) # This code is contributed by vipinyadav15799 |
C#
// C# program to find Vertical Sum in // a given Binary Tree using System; using System.Collections.Generic; // Class for a tree node class TreeNode { // data members public int key; public TreeNode left; public TreeNode right; // Accessor methods public int Key() { return key; } public TreeNode Left() { return left; } public TreeNode Right() { return right; } // Constructor public TreeNode( int key) { this .key = key; left = null ; right = null ; } // Methods to set left and right subtrees public void setLeft(TreeNode left) { this .left = left; } public void setRight(TreeNode right) { this .right = right; } } // Class for a Binary Tree class Tree { private TreeNode root; // Constructors public Tree() { root = null ; } public Tree(TreeNode n) { root = n; } // Method to be called by the consumer classes // like Main class public void VerticalSumMain() { VerticalSum(root); } // A wrapper over VerticalSumUtil() private void VerticalSum(TreeNode root) { // base case if (root == null ) { return ; } // Creates an empty hashMap hM Dictionary< int , int > hM = new Dictionary< int , int >(); // Calls the VerticalSumUtil() to store the // vertical sum values in hM VerticalSumUtil(root, 0, hM); // Prints the values stored by VerticalSumUtil() if (hM != null ) { Console.Write( "[" ); foreach (KeyValuePair< int , int > entry in hM) { Console.Write(entry.Key + " = " + entry.Value + ", " ); } Console.Write( "]" ); } } // Traverses the tree in in-order form and builds // a hashMap hM that contains the vertical sum private void VerticalSumUtil(TreeNode root, int hD, Dictionary< int , int > hM) { // base case if (root == null ) { return ; } // Store the values in hM for left subtree VerticalSumUtil(root.Left(), hD - 1, hM); // Update vertical sum for hD of this node int prevSum = 0; if (hM.ContainsKey(hD)) { prevSum = hM[hD]; hM[hD] = prevSum + root.Key(); } else hM.Add(hD, prevSum + root.Key()); // Store the values in hM for right subtree VerticalSumUtil(root.Right(), hD + 1, hM); } } // Driver Code public class GFG { public static void Main(String[] args) { /* Create the following Binary Tree 1 / 2 3 / / 4 5 6 7 */ TreeNode root = new TreeNode(1); root.setLeft( new TreeNode(2)); root.setRight( new TreeNode(3)); root.Left().setLeft( new TreeNode(4)); root.Left().setRight( new TreeNode(5)); root.Right().setLeft( new TreeNode(6)); root.Right().setRight( new TreeNode(7)); Tree t = new Tree(root); Console.WriteLine( "Following are the values of" + " vertical sums with the positions" + " of the columns with respect to root " ); t.VerticalSumMain(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find Vertical Sum in // a given Binary Tree // Node definition class newNode{ constructor(data){ this .left = null this .right = null this .data = data } } // Traverses the tree in in-order form and // populates a hashMap that contains the // vertical sum function verticalSumUtil(root, hd, map){ // Base case if (root == null ) return ; // Recur for left subtree verticalSumUtil(root.left, hd - 1, map) // Add val of current node to // map entry of corresponding hd if (map.has(hd) == true ) map.set(hd , map.get(hd) + root.data) else map.set(hd , root.data) // Recur for right subtree verticalSumUtil(root.right, hd + 1, map) } // Function to find vertical_sum function verticalSum(root){ // a dictionary to store sum of // nodes for each horizontal distance let map = new Map() // Populate the dictionary verticalSumUtil(root, 0, map); // Prints the values stored // by VerticalSumUtil() for (const [i,j] of map.entries()) document.write(i + ": " + j) } // Driver Code // Create the following Binary Tree // 1 // / // 2 3 /// / // 4 5 6 7 root = new newNode(1) root.left = new newNode(2) root.right = new newNode(3) root.left.left = new newNode(4) root.left.right = new newNode(5) root.right.left = new newNode(6) root.right.right = new newNode(7) root.right.left.right = new newNode(8); root.right.right.right = new newNode(9); document.write( "Following are the values of vertical sums with the positions of the columns with respect to root" ) verticalSum(root) // This code is contributed by shinjanpatra </script> |
输出
Following are the values of vertical sums with the positions of the columns with respect to root-2: 4-1: 20: 121: 112: 73: 9
二叉树|集合2中的垂直和（空间优化） 时间复杂度：O（nlogn） 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
