c++遍历求二叉树叶子节点

在 C 语言中，可以使用递归的方法遍历二叉树，求出所有的叶子节点。

首先，对于一个给定的节点，如果它的左子节点和右子节点都为空，那么它就是一个叶子节点，可以直接记录。如果不是叶子节点，则递归遍历其左子树和右子树。

下面是一个示例代码：

void findLeafNodes(Node* root)
{
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL)
    {
        // 当前节点是叶子节点，记录
        // ...
    }
    else
    {
        // 递归遍历左子树
        findLeafNodes(root->left);
        // 递归遍历右子树
        findLeafNodes(root->right);
    }
}

该代码需要根据具体的二叉树实现方式进行修改，以适配自己的二叉树结构。

相关问题

C++非递归求二叉树叶子节点个数

可以使用迭代法（非递归）来遍历二叉树，然后统计叶子节点的个数。下面是一个示例代码：

#include <iostream>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int countLeaves(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++; // 如果是叶子节点，计数器加1
        if (node->right) s.push(node->right); // 先将右子节点入栈
        if (node->left) s.push(node->left); // 再将左子节点入栈
    }
    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);
    cout << countLeaves(root) << endl; // 输出叶子节点个数
    return 0;
}

该算法的时间复杂度为O(n)，空间复杂度为O(h)，其中n是二叉树的节点个数，h是二叉树的高度。

c++二叉树的创建与遍历并求叶子节点数目完整代码

当然，下面是一个示例的完整代码，用于创建和遍历二叉树，并计算叶子节点数目。

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建二叉树
TreeNode* createBinaryTree() {
    int val;
    cin >> val;

    if (val == -1) {
        return NULL;
    }

    TreeNode* root = new TreeNode(val);
    cout << "Enter left child of " << val << ": ";
    root->left = createBinaryTree();
    cout << "Enter right child of " << val << ": ";
    root->right = createBinaryTree();

    return root;
}

// 遍历二叉树（前序遍历）
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 计算叶子节点数目
int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    cout << "Enter root value (-1 for NULL): ";
    TreeNode* root = createBinaryTree();

    cout << "Preorder traversal: ";
    preOrderTraversal(root);
    cout << endl;

    int leafNodeCount = countLeafNodes(root);
    cout << "Number of leaf nodes: " << leafNodeCount << endl;

    return 0;
}

这段代码实现了创建二叉树、前序遍历二叉树以及计算叶子节点数目的功能。你可以根据需要修改或扩展代码。