编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树,并判断这两棵二叉树是否相等。
时间: 2023-11-23 18:12:26 浏览: 82
以下是Python实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
```
其中,`buildTree`函数根据先序遍历序列和中序遍历序列建立二叉树,返回根节点。`isSameTree`函数用于判断两棵二叉树是否相等,递归地比较根节点以及左右子树。
阅读全文