数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装学
法律学用 C++ 检查给定的二叉树是否为 SumTree
本文我们将了解如何检查二叉树是否是 SumTree。现在的问题是，什么是 SumTree？SumTree 是一棵二叉树，其中一个节点将包含其子节点的和值。树的根包含其下方所有元素的总和。这是一个 SumTree 的示例 −
为了检查，我们将采用一个简单的技巧，即找到左右子树元素的和，如果和值与根相同，则它是 SumTree。这是一种递归方法。
示例
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left, *right;
};
int sum_of_nodes(node *root) {
if(root == NULL)
return 0;
return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
int left_sum, right_sum;
if(node == NULL || (node->left == NULL && node->right == NULL))
return 1;
left_sum = sum_of_nodes(node->left);
right_sum = sum_of_nodes(node->right);
if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
return 1;
return 0;
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(26);
root->left = getNode(10);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(6);
root->right->right = getNode(3);
if(isSumTree(root))
cout << "The tree is Sum Tree";
else
cout << "The tree is not a Sum Tree";
}输出
The tree is Sum Tree
更新于: 2019-10-22
164 查看
广告