資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中查詢單值子樹的數量
假設我們有一棵二叉樹。我們的任務是要計算給定樹中的單值子樹。單值子樹是一棵子樹，其中該樹的所有節點都包含相同的值。假設一棵樹如下所示 −
有四個單值子樹。它們如下所示 −
我們可以使用自下而上的方式解決這個問題。對於訪問的每個子樹，如果在其下生根的子樹為單值子樹，則返回 true，並將計數器增加 1。此處計數是遞迴呼叫的引用引數。並使用返回值來找出左右子樹是否是單值子樹。
示例
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left, *right;
};
Node* getNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool countSingleValuedSubtree(Node* root, int &count) {
if (root == NULL)
return true;
bool left = countSingleValuedSubtree(root->left, count);
bool right = countSingleValuedSubtree(root->right, count);
if (left == false || right == false)
return false;
if (root->left && root->data != root->left->data)
return false;
if (root->right && root->data != root->right->data)
return false;
count++;
return true;
}
int countSingleValSubtree(Node* root) {
int count = 0;
countSingleValuedSubtree(root, count);
return count;
}
int main() {
Node* root = getNode(5);
root->left = getNode(1);
root->right = getNode(5);
root->left->left = getNode(5);
root->left->right = getNode(5);
root->right->right = getNode(5);
cout << "Count of Single Valued Subtrees is: " << countSingleValSubtree(root);
}輸出
Count of Single Valued Subtrees is: 4
更新於: 2019 年 10 月 21 日
342 次瀏覽
廣告