通过二叉树的先序序列和中序序列构建二叉树,求叶子结点个数的递归和非递归
时间: 2024-01-23 21:49:26 浏览: 24
首先,根据先序序列确定根节点,然后根据根节点在中序序列中的位置,将中序序列分为左子树和右子树两部分。然后对左右子树分别递归构建二叉树。
以下是Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not inorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = buildTree(preorder, inorder[:index])
root.right = buildTree(preorder, inorder[index+1:])
return root
```
递归求叶子节点个数:
```python
def count_leaf_recursive(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_recursive(root.left) + count_leaf_recursive(root.right)
```
非递归求叶子节点个数,可以使用层次遍历,统计叶子节点个数:
```python
from collections import deque
def count_leaf_iterative(root):
if not root:
return 0
queue = deque([root])
count = 0
while queue:
node = queue.popleft()
if not node.left and not node.right:
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
```