找到树的根，其中每个节点的子id和都是给定的-yiteyi-C++库

考虑一个二叉树，其节点具有从1到n的ID，其中n是树中的节点数。该树由n对组成，其中每对代表节点id和子id之和。 例如：

null

Input : 1 5        2 0        3 0        4 0        5 5        6 5Output: 6Explanation: In this case, two trees can be made as follows and 6 is the root node.   6          6            /     5       1   4   /          1   4       5 /          / 2   3       2   3Input : 4 0Output: 4Explanation: Clearly 4 does not have any children and is theonly node i.e., the root node.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

乍一看，这个问题似乎是一个典型的树数据结构问题，但它可以按如下方式解决。除根节点外，每个节点id都显示在子节点和中。所以如果我们求所有ID的和，然后从所有子项和的和中减去它，我们得到根。

C++

                         // Find root of tree where children                       
                         // sum for every node id is given.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     findRoot(pair<                                     int                                     ,                                     int                                     > arr[],                                     int                                     n)                       
                         {                       
                                                 // Every node appears once as an id, and                       
                                                 // every node except for the root appears                       
                                                 // once in a sum.  So if we subtract all                       
                                                 // the sums from all the ids, we're left                       
                                                 // with the root id.                       
                                                 int                                     root = 0;                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 root += (arr[i].first - arr[i].second);                       
           
                                                 return                                     root;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 pair<                                     int                                     ,                                     int                                     > arr[] = {{1, 5}, {2, 0},                       
                                                 {3, 0}, {4, 0}, {5, 5}, {6, 5}};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 printf                                     (                                     "%d"                                     , findRoot(arr, n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Find root of tree where children                       
                         // sum for every node id is given.                       
           
                         class                                     GFG                       
                         {                       
           
                                                 static                                     class                                     pair                       
                                                 {                       
           
                                                 int                                     first, second;                       
           
                                                 public                                     pair(                                     int                                     first,                                     int                                     second)                       
                                                 {                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
           
                                                 }                       
           
                                                 static                                     int                                     findRoot(pair arr[],                                     int                                     n)                       
                                                 {                       
                                                 // Every node appears once as an id, and                       
                                                 // every node except for the root appears                       
                                                 // once in a sum. So if we subtract all                       
                                                 // the sums from all the ids, we're left                       
                                                 // with the root id.                       
                                                 int                                     root =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 root += (arr[i].first - arr[i].second);                       
                                                 }                       
           
                                                 return                                     root;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 pair arr[] = {                                     new                                     pair(                                     1                                     ,                                     5                                     ),                                     new                                     pair(                                     2                                     ,                                     0                                     ),                       
                                                 new                                     pair(                                     3                                     ,                                     0                                     ),                                     new                                     pair(                                     4                                     ,                                     0                                     ),                       
                                                 new                                     pair(                                     5                                     ,                                     5                                     ),                                     new                                     pair(                                     6                                     ,                                     5                                     )};                       
                                                 int                                     n = arr.length;                       
                                                 System.out.printf(                                     "%d"                                     , findRoot(arr, n));                       
                                                 }                       
           
                         }                       
           
                         /* This code is contributed by PrinciRaj1992 */                       

Python3

                         """Find root of tree where children                       
                         sum for every node id is given"""                       
           
                         def                                     findRoot(arr, n) :                       
           
                                                 # Every node appears once as an id, and                       
                                                 # every node except for the root appears                       
                                                 # once in a sum. So if we subtract all                       
                                                 # the sums from all the ids, we're left                       
                                                 # with the root id.                       
                                                 root                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 root                                     +                                     =                                     (arr[i][                                     0                                     ]                                     -                                     arr[i][                                     1                                     ])                       
                                                 return                                     root                       
                                   
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
           
                                                 arr                                     =                                     [[                                     1                                     ,                                     5                                     ], [                                     2                                     ,                                     0                                     ],                       
                                                 [                                     3                                     ,                                     0                                     ], [                                     4                                     ,                                     0                                     ],                       
                                                 [                                     5                                     ,                                     5                                     ], [                                     6                                     ,                                     5                                     ]]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 print                                     (findRoot(arr, n))                       
           
                         # This code is contributed                       
                         # by SHUBHAMSINGH10                       

C#

                         // C# Find root of tree where children                       
                         // sum for every node id is given.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
           
                                                 public                                     class                                     pair                       
                                                 {                       
           
                                                 public                                     int                                     first, second;                       
           
                                                 public                                     pair(                                     int                                     first,                                     int                                     second)                       
                                                 {                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
           
                                                 }                       
           
                                                 static                                     int                                     findRoot(pair []arr,                                     int                                     n)                       
                                                 {                       
                                                 // Every node appears once as an id, and                       
                                                 // every node except for the root appears                       
                                                 // once in a sum. So if we subtract all                       
                                                 // the sums from all the ids, we're left                       
                                                 // with the root id.                       
                                                 int                                     root = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 root += (arr[i].first - arr[i].second);                       
                                                 }                       
           
                                                 return                                     root;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 pair []arr = {                                     new                                     pair(1, 5),                                     new                                     pair(2, 0),                       
                                                 new                                     pair(3, 0),                                     new                                     pair(4, 0),                       
                                                 new                                     pair(5, 5),                                     new                                     pair(6, 5)};                       
                                                 int                                     n = arr.Length;                       
                                                 Console.Write(                                     "{0}"                                     , findRoot(arr, n));                       
                                                 }                       
           
                         }                       
           
                         /* This code is contributed by PrinciRaj1992 */                       

Javascript

                         <script>                       
           
                         // Javascript: Find root of tree where children                       
                         // sum for every node id is given.                       
           
                         /*Every node appears once as an id, and                       
                         every node except for the root appears                       
                         once in a sum. So if we subtract all                       
                         the sums from all the ids, we're left                       
                         with the root id. */                       
           
           
                         const findRoot = (nodeList) => {                       
                                                 let root = 0;                       
                                                 nodeList.forEach(element =>                       
                                                 root+=(Number(element[0]) - Number(element[1])));                       
                                                 return                                     root ;                       
                         }                       
           
           
                         let nodeList = [[1, 5], [2, 0],                       
                                                 [3, 0], [4, 0],                       
                                                 [5, 5], [6, 5]];                       
                         let root = findRoot(nodeList);                       
                         document.write(root);                       
           
                         // This code is contributed by bharathmkulkarni                       
           
                         </script>                       

输出：

本文由 苏尼迪·乔杜里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章