数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装研究
法律研究使用 C++ 检查二叉树中的儿童求和属性
假设我们有一棵二叉树。二叉树在满足以下属性时才有效。
- 每个节点都应包含与左右子节点值相加所得相同的数据值。如果任何一侧没有子节点，则将该节点视为 0。
假设存在以下一棵符合给定属性的树。
没有其他方法可以检查这一点，我们只能递归遍历该树，如果节点及其两个子节点都满足该属性，则返回 true，否则返回 false。
示例
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
bool isValidBinaryTree(node* nd) {
int left_data = 0, right_data = 0;
if(nd == NULL || (nd->left == NULL && nd->right == NULL))
return 1;
else{
if(nd->left != NULL)
left_data = nd->left->data;
if(nd->right != NULL)
right_data = nd->right->data;
if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
return true;
else
return false;
}
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(10);
root->left = getNode(8);
root->right = getNode(2);
root->left->left = getNode(3);
root->left->right = getNode(5);
root->right->right = getNode(2);
if(isValidBinaryTree(root))
cout << "The tree satisfies the children sum property ";
else
cout << "The tree does not satisfy the children sum property ";
}输出
The tree satisfies the children sum property
更新时间： 2019-10-21
79 次浏览
广告