資料結構
網路
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 檢視
廣告