应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作
时间: 2023-10-09 14:11:15 浏览: 95
判断两棵二叉树是否相等,可以通过对两棵二叉树进行遍历,比较每个节点的值是否相等来实现。
具体来说,可以采用先序遍历、中序遍历或后序遍历中的一种方式,将两棵二叉树分别遍历一遍,得到两个序列,然后比较这两个序列是否相等即可。
以下是采用先序遍历实现判断两棵二叉树相等的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# 判断两个节点是否相等
def isSameNode(node1, node2):
if not node1 and not node2:
return True
elif not node1 or not node2:
return False
else:
return node1.val == node2.val
# 先序遍历二叉树,返回遍历结果
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 比较两个序列是否相等
return preorderTraversal(p) == preorderTraversal(q)
```
在上述代码中,`isSameNode`函数用来判断两个节点是否相等,`preorderTraversal`函数用来先序遍历二叉树并返回遍历结果,`isSameTree`函数则是将这两个函数结合起来判断两棵二叉树是否相等。
阅读全文