用C++通过二叉树的先序序列和中序序列构建二叉树,求叶子结点个数的递归和非递归

1. 通过先序序列和中序序列构建二叉树

二叉树的先序遍历序列和中序遍历序列都是按照根节点、左子树、右子树的顺序遍历的。因此，我们可以通过先序序列找到根节点，再在中序序列中找到根节点的位置，从而确定左子树和右子树的中序遍历序列。接下来，我们可以递归地构建左子树和右子树。

代码实现如下：

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

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return NULL;
    }
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

2. 递归求叶子节点个数

二叉树的叶子节点是指没有左子树和右子树的节点。因此，我们可以通过递归遍历二叉树，统计叶子节点的个数。

代码实现如下：

int countLeaves(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

3. 非递归求叶子节点个数

非递归求叶子节点个数需要使用栈来辅助遍历二叉树。我们可以采用深度优先遍历算法，遍历过程中统计叶子节点的个数。具体实现如下：

int countLeaves(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    stack<TreeNode*> s;
    s.push(root);
    int count = 0;
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->left == NULL && node->right == NULL) {
            count++;
        }
        if (node->right != NULL) {
            s.push(node->right);
        }
        if (node->left != NULL) {
            s.push(node->left);
        }
    }
    return count;
}

以上就是用C++通过二叉树的先序序列和中序序列构建二叉树，以及递归和非递归求叶子结点个数的方法。