利用递归遍历算法建立一颗二元树,输出先序遍历序列及该二元树中全部的叶子节点
时间: 2024-03-17 08:40:59 浏览: 13
好的,我来解答你的问题。以下是递归遍历算法建立一颗二元树的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = build_tree(preorder[1:index+1], inorder[:index])
root.right = build_tree(preorder[index+1:], inorder[index+1:])
return root
```
其中,`preorder` 表示二元树的先序遍历序列,`inorder` 表示二元树的中序遍历序列。这段代码的时间复杂度为 $O(n)$,其中 $n$ 是二元树的节点数。
下面是输出先序遍历序列及该二元树中全部的叶子节点的代码:
```python
def preorder_traversal(root):
if not root:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
def get_leaf_nodes(root):
if not root:
return []
if not root.left and not root.right:
return [root.val]
res = []
res += get_leaf_nodes(root.left)
res += get_leaf_nodes(root.right)
return res
# 示例代码
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = build_tree(preorder, inorder)
print(preorder_traversal(root)) # 输出:[1, 2, 4, 5, 3, 6, 7]
print(get_leaf_nodes(root)) # 输出:[4, 5, 6, 7]
```
其中,`preorder_traversal` 函数用于输出二元树的先序遍历序列,`get_leaf_nodes` 函数用于输出二元树中的全部叶子节点。这段代码的时间复杂度也是 $O(n)$,其中 $n$ 是二元树的节点数。