已知二叉树的先序和中序序列,构造出相应 的二叉树 先序:ABCDEFGHIJ 中序:CDBFEAIHGj,画出该二叉树
时间: 2023-11-17 12:03:32 浏览: 129
以下是构造二叉树的步骤:
1. 从先序序列中取出第一个元素作为根节点。
2. 在中序序列中找到根节点的位置,根节点左边的元素为左子树的中序序列,右边的元素为右子树的中序序列。
3. 根据左子树的中序序列的长度,在先序序列中找到左子树的先序序列,右边的元素为右子树的先序序列。
4. 递归地构造左子树和右子树。
根据上述步骤,可以得到以下代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
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
preorder = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
inorder = ['C', 'D', 'B', 'F', 'E', 'A', 'I', 'H', 'G', 'J']
root = build
阅读全文