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

1. 递归解法：

先构建二叉树，然后对二叉树进行递归遍历，统计叶子节点的个数。

二叉树的先序序列和中序序列可以唯一确定一棵二叉树，因此可以通过这两个序列构建二叉树。具体步骤如下：

1. 在先序序列中找到第一个元素作为根节点。
2. 在中序序列中找到根节点，将中序序列分为左子树和右子树两部分。
3. 根据左子树和右子树的长度，在先序序列中分别确定左子树和右子树的范围。
4. 递归构建左右子树，直到序列为空。

构建完二叉树之后，对二叉树进行递归遍历，统计叶子节点的个数即可。

代码如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def buildTree(preorder, inorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    idx = inorder.index(root.val)
    root.left = buildTree(preorder[1:idx+1], inorder[:idx])
    root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
    return root

def countLeafNode(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return countLeafNode(root.left) + countLeafNode(root.right)

preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(countLeafNode(root))  # 输出 4

2. 非递归解法：

使用栈来辅助遍历二叉树，统计叶子节点的个数。

具体步骤如下：

1. 初始化栈，将根节点入栈。
2. 如果栈不为空，弹出栈顶元素。
3. 如果弹出的节点是叶子节点，统计叶子节点个数。
4. 如果弹出的节点有右子树，将右子树入栈。
5. 如果弹出的节点有左子树，将左子树入栈。
6. 重复步骤 2-5，直到栈为空。

代码如下：

def countLeafNode(root):
    if not root:
        return 0
    stack = [root]
    count = 0
    while stack:
        node = stack.pop()
        if not node.left and not node.right:
            count += 1
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return count

preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(countLeafNode(root))  # 输出 4

注意，这里使用的是先序遍历的方式，也可以使用中序遍历或后序遍历的方式，只需要修改入栈的顺序即可。