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

通过先序序列和中序序列构建二叉树的过程可以分为以下几步：

1. 从先序序列中取出第一个节点作为根节点；
2. 在中序序列中找到根节点的位置，将中序序列分成左子树和右子树两部分；
3. 根据左子树的节点数量，在先序序列中找到左子树的先序序列和右子树的先序序列；
4. 递归构建左子树和右子树。

以下是一个用C++实现的通过先序序列和中序序列构建二叉树的函数：

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

用递归算法求二叉树叶子节点个数的代码如下：

int countLeafNodes(TreeNode* root) {
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

用非递归算法求二叉树叶子节点个数的代码如下：

int countLeafNodes(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;
        }
        if (node->left) {
            s.push(node->left);
        }
        if (node->right) {
            s.push(node->right);
        }
    }
    return count;
}