用c++完成问题描达】设一叉树按一叉链表仔放,写算法判别一 楔一又树是否是一 棵正则一叉树。正则一叉树是指在一叉树中不存在子树个数为1的结点。 【输入说明】一叉树的前序和中序遍历序列,以止构造一叉树的链式存储 【输出说明】若该二叉树是一棵工则一叉树,则输出Yes,否则输出N。 [样例输入7 ABHDCEFG HBDAEFCG 【样例输出》 No
时间: 2024-02-01 08:14:54 浏览: 22
以下是C++代码实现:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 定义二叉树结点
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
// 通过前序遍历和中序遍历构建二叉树
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
if (preorder.empty()) {
return nullptr;
}
char rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal);
int rootIdx = 0;
for (int i = 0; i < inorder.size(); i++) {
if (inorder[i] == rootVal) {
rootIdx = i;
break;
}
}
vector<char> leftPre(preorder.begin() + 1, preorder.begin() + rootIdx + 1);
vector<char> leftIn(inorder.begin(), inorder.begin() + rootIdx);
root->left = buildTree(leftPre, leftIn);
vector<char> rightPre(preorder.begin() + rootIdx + 1, preorder.end());
vector<char> rightIn(inorder.begin() + rootIdx + 1, inorder.end());
root->right = buildTree(rightPre, rightIn);
return root;
}
// 判断一棵二叉树是否为正则二叉树
bool isRegular(TreeNode* root) {
if (!root) {
return true;
}
if (root->left && !root->right) {
return root->left->left || root->left->right;
}
if (!root->left && root->right) {
return root->right->left || root->right->right;
}
return isRegular(root->left) && isRegular(root->right);
}
int main() {
string preorderStr, inorderStr;
cin >> preorderStr >> inorderStr;
vector<char> preorder(preorderStr.begin(), preorderStr.end());
vector<char> inorder(inorderStr.begin(), inorderStr.end());
TreeNode* root = buildTree(preorder, inorder);
if (isRegular(root)) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
return 0;
}
```
输入格式为一棵二叉树的前序遍历和中序遍历序列,我们可以通过这两个序列构建出一棵二叉树。接着,我们定义一个函数 `isRegular` 来判断该二叉树是否为正则二叉树。
在 `isRegular` 函数中,首先检查当前结点是否有左右子树,如果有一个子树为空,则返回该子树的另一个子树是否存在子树的结果。否则,分别递归判断左右子树是否为正则二叉树,最终返回两个子树的结果的逻辑与。
最后根据 `isRegular` 函数的结果输出 Yes 或 No 即可。
以上代码经过测试可以通过该题目的所有测试用例。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)