C++用递归和非递归求叶子数的主函数的源代码
时间: 2023-06-29 18:15:11 浏览: 34
好的,以下是 C++ 的源代码:
1. 递归方法:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int countLeaves_recursive(TreeNode* root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return 1;
}
return countLeaves_recursive(root->left) + countLeaves_recursive(root->right);
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int leaves = countLeaves_recursive(root);
cout << "The number of leaves is: " << leaves << endl;
return 0;
}
```
2. 非递归方法:
```cpp
int countLeaves_iterative(TreeNode* root) {
if (!root) {
return 0;
}
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (!node->left && !node->right) {
count++;
} else {
if (node->left) {
s.push(node->left);
}
if (node->right) {
s.push(node->right);
}
}
}
return count;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int leaves = countLeaves_iterative(root);
cout << "The number of leaves is: " << leaves << endl;
return 0;
}
```
希望这些代码能够帮助到你!