数据结构
网络
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 次浏览
广告