设计并验证如下算法:按中序序列建立两棵二叉树的二叉链表结构,判断两棵二叉树是否相等
时间: 2023-06-25 17:05:51 浏览: 94
算法设计:
1. 分别按中序遍历建立两棵二叉树的二叉链表结构;
2. 依次比较两棵二叉树的每个节点,判断节点值和左右子树是否相等;
3. 若所有节点都相等,则两棵二叉树相等,否则不相等。
算法实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(inorder):
if not inorder:
return None
# 找到中间节点,作为根节点
mid = len(inorder) // 2
root = TreeNode(inorder[mid])
# 递归建立左右子树
root.left = buildTree(inorder[:mid])
root.right = buildTree(inorder[mid+1:])
return root
def isSameTree(p, q):
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
else:
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
def isTwoTreesEqual(inorder1, inorder2):
root1 = buildTree(inorder1)
root2 = buildTree(inorder2)
return isSameTree(root1, root2)
```
算法验证:
测试用例1:
```python
inorder1 = [1, 2, 3]
inorder2 = [1, 2, 3]
print(isTwoTreesEqual(inorder1, inorder2)) # True
```
测试用例2:
```python
inorder1 = [1, 2, 3]
inorder2 = [1, 3, 2]
print(isTwoTreesEqual(inorder1, inorder2)) # False
```
测试用例3:
```python
inorder1 = []
inorder2 = []
print(isTwoTreesEqual(inorder1, inorder2)) # True
```
上述算法在时间和空间复杂度上都是 $O(n)$,其中 $n$ 是节点数。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)