编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树,并判断这两棵二叉树是否相等
时间: 2023-11-23 07:03:52 浏览: 95
思路:
1. 根据先序遍历和中序遍历的特点,可以得到先序遍历的第一个节点是根节点,根据根节点在中序遍历中的位置可以得到左子树和右子树的中序遍历序列。
2. 然后递归地构建左子树和右子树。
3. 构建完毕之后,比较两棵树是否相等,可以先比较根节点是否相等,然后递归地比较左子树和右子树。
代码实现:
```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_val = preorder[0]
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+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)
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root1 = buildTree(preorder, inorder)
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root2 = buildTree(preorder, inorder)
print(isSameTree(root1, root2)) # True
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root3 = buildTree(preorder, inorder)
preorder = [1, 2, 4, 5, 3, 7, 6]
inorder = [4, 2, 5, 1, 6, 3, 7]
root4 = buildTree(preorder, inorder)
print(isSameTree(root3, root4)) # False
```
输出结果为:
```
True
False
```
阅读全文