编写一个函数，如果给定的二叉树为SumTree else false，则返回true。SumTree是一种二叉树，其中一个节点的值等于其左子树和右子树中存在的节点之和。空树是SumTree，空树的和可以被认为是0。叶节点也被视为SumTree。
null
下面是SumTree的一个例子。
26 / 10 3 / 4 6 3
方法1（简单） 获取左子树和右子树中的节点之和。检查计算的总和是否等于根的数据。此外，递归地检查左子树和右子树是否为sumtree。
C++
// C++ program to check if Binary tree // is sum tree or not #include <iostream> using namespace std; // A binary tree node has data, // left child and right child struct node { int data; struct node* left; struct node* right; }; // A utility function to get the sum // of values in tree with root as root int sum( struct node *root) { if (root == NULL) return 0; return sum(root->left) + root->data + sum(root->right); } // Returns 1 if sum property holds for // the given node and both of its children int isSumTree( struct node* node) { int ls, rs; // If node is NULL or it's a leaf // node then return true if (node == NULL || (node->left == NULL && node->right == NULL)) return 1; // Get sum of nodes in left and // right subtrees ls = sum(node->left); rs = sum(node->right); // If the node and both of its // children satisfy the property // return 1 else 0 if ((node->data == ls + rs) && isSumTree(node->left) && isSumTree(node->right)) return 1; return 0; } // Helper function that allocates a new node // with the given data and NULL left and right // pointers. struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Driver code int main() { struct node *root = newNode(26); root->left = newNode(10); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(6); root->right->right = newNode(3); if (isSumTree(root)) cout << "The given tree is a SumTree " ; else cout << "The given tree is not a SumTree " ; getchar (); return 0; } // This code is contributed by khushboogoyal499 |
C
// C program to check if Binary tree // is sum tree or not #include <stdio.h> #include <stdlib.h> /* A binary tree node has data, left child and right child */ struct node { int data; struct node* left; struct node* right; }; /* A utility function to get the sum of values in tree with root as root */ int sum( struct node *root) { if (root == NULL) return 0; return sum(root->left) + root->data + sum(root->right); } /* returns 1 if sum property holds for the given node and both of its children */ int isSumTree( struct node* node) { int ls, rs; /* If node is NULL or it's a leaf node then return true */ if (node == NULL || (node->left == NULL && node->right == NULL)) return 1; /* Get sum of nodes in left and right subtrees */ ls = sum(node->left); rs = sum(node->right); /* if the node and both of its children satisfy the property return 1 else 0*/ if ((node->data == ls + rs)&& isSumTree(node->left) && isSumTree(node->right)) return 1; return 0; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } /* Driver program to test above function */ int main() { struct node *root = newNode(26); root->left = newNode(10); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(6); root->right->right = newNode(3); if (isSumTree(root)) printf ( "The given tree is a SumTree." ); else printf ( "The given tree is not a SumTree." ); getchar (); return 0; } |
JAVA
// Java program to check if Binary tree // is sum tree or not import java.io.*; // A binary tree node has data, // left child and right child class Node { int data; Node left, right, nextRight; // Helper function that allocates a new node // with the given data and NULL left and right // pointers. Node( int item) { data = item; left = right = null ; } } class BinaryTree { public static Node root; // A utility function to get the sum // of values in tree with root as root static int sum(Node node) { if (node == null ) { return 0 ; } return (sum(node.left) + node.data+sum(node.right)); } // Returns 1 if sum property holds for // the given node and both of its children static int isSumTree(Node node) { int ls,rs; // If node is NULL or it's a leaf // node then return true if (node == null || (node.left == null && node.right == null )) { return 1 ; } // Get sum of nodes in left and // right subtrees ls = sum(node.left); rs = sum(node.right); // If the node and both of its // children satisfy the property // return 1 else 0 if ((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0 ) { return 1 ; } return 0 ; } // Driver code public static void main (String[] args) { BinaryTree tree= new BinaryTree(); tree.root= new Node( 26 ); tree.root.left= new Node( 10 ); tree.root.right= new Node( 3 ); tree.root.left.left= new Node( 4 ); tree.root.left.right= new Node( 6 ); tree.root.right.right= new Node( 3 ); if (isSumTree(root) != 0 ) { System.out.println( "The given tree is a SumTree" ); } else { System.out.println( "The given tree is not a SumTree" ); } } } // This code is contributed by rag2127 |
Python3
# Python3 program to implement # the above approach # A binary tree node has data, # left child and right child class node: def __init__( self , x): self .data = x self .left = None self .right = None # A utility function to get the sum # of values in tree with root as root def sum (root): if (root = = None ): return 0 return ( sum (root.left) + root.data + sum (root.right)) # returns 1 if sum property holds # for the given node and both of # its children def isSumTree(node): # ls, rs # If node is None or it's a leaf # node then return true if (node = = None or (node.left = = None and node.right = = None )): return 1 # Get sum of nodes in left and # right subtrees ls = sum (node.left) rs = sum (node.right) # if the node and both of its children # satisfy the property return 1 else 0 if ((node.data = = ls + rs) and isSumTree(node.left) and isSumTree(node.right)): return 1 return 0 # Driver code if __name__ = = '__main__' : root = node( 26 ) root.left = node( 10 ) root.right = node( 3 ) root.left.left = node( 4 ) root.left.right = node( 6 ) root.right.right = node( 3 ) if (isSumTree(root)): print ( "The given tree is a SumTree " ) else : print ( "The given tree is not a SumTree " ) # This code is contributed by Mohit Kumar 29 |
C#
// C# program to check if Binary tree // is sum tree or not using System; // A binary tree node has data, // left child and right child public class Node { public int data; public Node left, right, nextRight; // Helper function that allocates a new node // with the given data and NULL left and right // pointers. public Node( int item) { data = item; left = right = null ; } } class BinaryTree { public Node root; // A utility function to get the sum // of values in tree with root as root int sum(Node node) { if (node == null ) { return 0; } return (sum(node.left) + node.data+sum(node.right)); } // Returns 1 if sum property holds for // the given node and both of its children int isSumTree(Node node) { int ls,rs; // If node is NULL or it's a leaf // node then return true if (node == null || (node.left == null && node.right == null )) { return 1; } // Get sum of nodes in left and // right subtrees ls = sum(node.left); rs = sum(node.right); // If the node and both of its // children satisfy the property // return 1 else 0 if ((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0) { return 1; } return 0; } // Driver code public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(26); tree.root.left = new Node(10); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(6); tree.root.right.right = new Node(3); if (tree.isSumTree(tree.root) != 0) { Console.WriteLine( "The given tree is a SumTree" ); } else { Console.WriteLine( "The given tree is not a SumTree" ); } } } // This code is contributed by Pratham76 |
Javascript
<script> // Javascript program to check if Binary tree // is sum tree or not // A binary tree node has data, // left child and right child class Node { // Helper function that allocates a new node // with the given data and NULL left and right // pointers. constructor(x) { this .data = x; this .left = null ; this .right = null ; } } let root; // A utility function to get the sum // of values in tree with root as root function sum(node) { if (node == null ) { return 0; } return (sum(node.left) + node.data+sum(node.right)); } // Returns 1 if sum property holds for // the given node and both of its children function isSumTree(node) { let ls,rs; // If node is NULL or it's a leaf // node then return true if (node == null || (node.left == null && node.right == null )) { return 1; } // Get sum of nodes in left and // right subtrees ls = sum(node.left); rs = sum(node.right); // If the node and both of its // children satisfy the property // return 1 else 0 if ((node.data == ls + rs) && isSumTree(node.left) != 0 && isSumTree(node.right) != 0) { return 1; } return 0; } // Driver code root = new Node(26) root.left= new Node(10) root.right = new Node(3) root.left.left = new Node(4) root.left.right = new Node(6) root.right.right = new Node(3) if (isSumTree(root) != 0) { document.write( "The given tree is a SumTree" ); } else { document.write( "The given tree is not a SumTree" ); } // This code is contributed by unknown2108 </script> |
输出
The given tree is a SumTree
时间复杂度：最坏情况下为O（n^2）。最坏的情况发生在歪斜的树上。
方法2（棘手） 方法1使用sum（）获取左右子树中的节点之和。方法2使用以下规则直接获取总和。 1） 如果该节点是叶节点，则与该节点同根的子树之和等于该节点的值。 2） 如果该节点不是叶节点，则以该节点为根的子树的和是该节点值的两倍（假设以该节点为根的树是SumTree）。
C++
// C++ program to check if Binary tree // is sum tree or not #include<bits/stdc++.h> using namespace std; /* A binary tree node has data, left child and right child */ struct node { int data; node* left; node* right; }; /* Utility function to check if the given node is leaf or not */ int isLeaf(node *node) { if (node == NULL) return 0; if (node->left == NULL && node->right == NULL) return 1; return 0; } /* returns 1 if SumTree property holds for the given tree */ int isSumTree(node* node) { int ls; // for sum of nodes in left subtree int rs; // for sum of nodes in right subtree /* If node is NULL or it's a leaf node then return true */ if (node == NULL || isLeaf(node)) return 1; if ( isSumTree(node->left) && isSumTree(node->right)) { // Get the sum of nodes in left subtree if (node->left == NULL) ls = 0; else if (isLeaf(node->left)) ls = node->left->data; else ls = 2 * (node->left->data); // Get the sum of nodes in right subtree if (node->right == NULL) rs = 0; else if (isLeaf(node->right)) rs = node->right->data; else rs = 2 * (node->right->data); /* If root's data is equal to sum of nodes in left and right subtrees then return 1 else return 0*/ return (node->data == ls + rs); } return 0; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode( int data) { node* node1 = new node(); node1->data = data; node1->left = NULL; node1->right = NULL; return (node1); } /* Driver code */ int main() { node *root = newNode(26); root->left = newNode(10); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(6); root->right->right = newNode(3); if (isSumTree(root)) cout << "The given tree is a SumTree " ; else cout << "The given tree is not a SumTree " ; return 0; } // This code is contributed by rutvik_56 |
C
// C program to check if Binary tree // is sum tree or not #include <stdio.h> #include <stdlib.h> /* A binary tree node has data, left child and right child */ struct node { int data; struct node* left; struct node* right; }; /* Utility function to check if the given node is leaf or not */ int isLeaf( struct node *node) { if (node == NULL) return 0; if (node->left == NULL && node->right == NULL) return 1; return 0; } /* returns 1 if SumTree property holds for the given tree */ int isSumTree( struct node* node) { int ls; // for sum of nodes in left subtree int rs; // for sum of nodes in right subtree /* If node is NULL or it's a leaf node then return true */ if (node == NULL || isLeaf(node)) return 1; if ( isSumTree(node->left) && isSumTree(node->right)) { // Get the sum of nodes in left subtree if (node->left == NULL) ls = 0; else if (isLeaf(node->left)) ls = node->left->data; else ls = 2*(node->left->data); // Get the sum of nodes in right subtree if (node->right == NULL) rs = 0; else if (isLeaf(node->right)) rs = node->right->data; else rs = 2*(node->right->data); /* If root's data is equal to sum of nodes in left and right subtrees then return 1 else return 0*/ return (node->data == ls + rs); } return 0; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } /* Driver program to test above function */ int main() { struct node *root = newNode(26); root->left = newNode(10); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(6); root->right->right = newNode(3); if (isSumTree(root)) printf ( "The given tree is a SumTree " ); else printf ( "The given tree is not a SumTree " ); getchar (); return 0; } |
JAVA
// Java program to check if Binary tree is sum tree or not /* A binary tree node has data, left child and right child */ class Node { int data; Node left, right, nextRight; Node( int item) { data = item; left = right = nextRight = null ; } } class BinaryTree { Node root; /* Utility function to check if the given node is leaf or not */ int isLeaf(Node node) { if (node == null ) return 0 ; if (node.left == null && node.right == null ) return 1 ; return 0 ; } /* returns 1 if SumTree property holds for the given tree */ int isSumTree(Node node) { int ls; // for sum of nodes in left subtree int rs; // for sum of nodes in right subtree /* If node is NULL or it's a leaf node then return true */ if (node == null || isLeaf(node) == 1 ) return 1 ; if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0 ) { // Get the sum of nodes in left subtree if (node.left == null ) ls = 0 ; else if (isLeaf(node.left) != 0 ) ls = node.left.data; else ls = 2 * (node.left.data); // Get the sum of nodes in right subtree if (node.right == null ) rs = 0 ; else if (isLeaf(node.right) != 0 ) rs = node.right.data; else rs = 2 * (node.right.data); /* If root's data is equal to sum of nodes in left and right subtrees then return 1 else return 0*/ if ((node.data == rs + ls)) return 1 ; else return 0 ; } return 0 ; } /* Driver program to test above functions */ public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 26 ); tree.root.left = new Node( 10 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 6 ); tree.root.right.right = new Node( 3 ); if (tree.isSumTree(tree.root) != 0 ) System.out.println( "The given tree is a SumTree" ); else System.out.println( "The given tree is not a SumTree" ); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to check if # Binary tree is sum tree or not # A binary tree node has data, # left child and right child class node: def __init__( self , x): self .data = x self .left = None self .right = None def isLeaf(node): if (node = = None ): return 0 if (node.left = = None and node.right = = None ): return 1 return 0 # A utility function to get the sum # of values in tree with root as root def sum (root): if (root = = None ): return 0 return ( sum (root.left) + root.data + sum (root.right)) # returns 1 if SumTree property holds # for the given tree def isSumTree(node): # If node is None or # it's a leaf node then return true if (node = = None or isLeaf(node)): return 1 if (isSumTree(node.left) and isSumTree(node.right)): # Get the sum of nodes in left subtree if (node.left = = None ): ls = 0 elif (isLeaf(node.left)): ls = node.left.data else : ls = 2 * (node.left.data) # Get the sum of nodes in right subtree if (node.right = = None ): rs = 0 elif (isLeaf(node.right)): rs = node.right.data else : rs = 2 * (node.right.data) # If root's data is equal to sum of nodes # in left and right subtrees then return 1 # else return 0 return (node.data = = ls + rs) return 0 # Driver code if __name__ = = '__main__' : root = node( 26 ) root.left = node( 10 ) root.right = node( 3 ) root.left.left = node( 4 ) root.left.right = node( 6 ) root.right.right = node( 3 ) if (isSumTree(root)): print ( "The given tree is a SumTree " ) else : print ( "The given tree is not a SumTree " ) # This code is contributed by kirtishsurangalikar |
C#
// C# program to check if Binary tree // is sum tree or not using System; // A binary tree node has data, left // child and right child public class Node { public int data; public Node left, right, nextRight; public Node( int d) { data = d; left = right = nextRight = null ; } } public class BinaryTree{ public static Node root; // Utility function to check if // the given node is leaf or not public int isLeaf(Node node) { if (node == null ) return 0; if (node.left == null && node.right == null ) return 1; return 0; } // Returns 1 if SumTree property holds // for the given tree public int isSumTree(Node node) { // For sum of nodes in left subtree int ls; // For sum of nodes in right subtree int rs; // If node is NULL or it's a leaf // node then return true if (node == null || isLeaf(node) == 1) return 1; if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0) { // Get the sum of nodes in left subtree if (node.left == null ) ls = 0; else if (isLeaf(node.left) != 0) ls = node.left.data; else ls = 2 * (node.left.data); // Get the sum of nodes in right subtree if (node.right == null ) rs = 0; else if (isLeaf(node.right) != 0) rs = node.right.data; else rs = 2 * (node.right.data); // If root's data is equal to sum of // nodes in left and right subtrees // then return 1 else return 0 if ((node.data == rs + ls)) return 1; else return 0; } return 0; } // Driver code static public void Main() { BinaryTree tree = new BinaryTree(); BinaryTree.root = new Node(26); BinaryTree.root.left = new Node(10); BinaryTree.root.right = new Node(3); BinaryTree.root.left.left = new Node(4); BinaryTree.root.left.right = new Node(6); BinaryTree.root.right.right = new Node(3); if (tree.isSumTree(BinaryTree.root) != 0) { Console.WriteLine( "The given tree is a SumTree" ); } else { Console.WriteLine( "The given tree is " + "not a SumTree" ); } } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // JavaScript program to check // if Binary tree is sum tree or not class Node { constructor(item) { this .data = item; this .left = null ; this .right = null ; this .nextRight = null ; } } let root; /* Utility function to check if the given node is leaf or not */ function isLeaf(node) { if (node == null ) return 0; if (node.left == null && node.right == null ) return 1; return 0; } /* returns 1 if SumTree property holds for the given tree */ function isSumTree(node) { let ls; // for sum of nodes in left subtree let rs; // for sum of nodes in right subtree /* If node is NULL or it's a leaf node then return true */ if (node == null || isLeaf(node) == 1) return 1; if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0) { // Get the sum of nodes in left subtree if (node.left == null ) ls = 0; else if (isLeaf(node.left) != 0) ls = node.left.data; else ls = 2 * (node.left.data); // Get the sum of nodes in right subtree if (node.right == null ) rs = 0; else if (isLeaf(node.right) != 0) rs = node.right.data; else rs = 2 * (node.right.data); /* If root's data is equal to sum of nodes in left and right subtrees then return 1 else return 0*/ if ((node.data == rs + ls)) return 1; else return 0; } return 0; } root = new Node(26); root.left = new Node(10); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(6); root.right.right = new Node(3); if (isSumTree(root) != 0) document.write( "The given tree is a SumTree" ); else document.write( "The given tree is not a SumTree" ); </script> |
输出：
The given tree is a SumTree
时间复杂性： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
