資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告