构造二叉树并且输入输出
时间: 2023-11-14 07:18:29 浏览: 40
构造二叉树可以通过递归的方式进行。二叉树的每个节点有一个值,以及指向左右子节点的指针。下面是一个简单的二叉树节点的定义:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
递归构造二叉树的思路是,先构造左子树,再构造右子树,最后将左右子树连接到当前节点上。具体实现如下:
```python
def build_tree(nums):
def build_node(i, j):
if i > j:
return None
mid = (i + j) // 2
node = TreeNode(nums[mid])
node.left = build_node(i, mid - 1)
node.right = build_node(mid + 1, j)
return node
return build_node(0, len(nums) - 1)
```
上面这个函数可以构造一棵高度平衡的二叉树,输入一个有序数组 `nums`,输出对应二叉树的根节点。这个函数的时间复杂度是 $O(n)$,其中 $n$ 是数组的长度。下面是一个简单的测试:
```python
def inorder_traversal(node):
if node:
inorder_traversal(node.left)
print(node.val, end=' ')
inorder_traversal(node.right)
nums = [1, 2, 3, 4, 5, 6, 7]
root = build_tree(nums)
inorder_traversal(root) # 输出:1 2 3 4 5 6 7
```
这个测试先构造了一个有序数组 `[1, 2, 3, 4, 5, 6, 7]` 对应的二叉树,然后对这棵二叉树进行中序遍历,输出节点的值。