|
| 1 | +## 相同的树 |
| 2 | +给定两个二叉树，编写一个函数来检验它们是否相同。 |
| 3 | + |
| 4 | +如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 |
| 5 | + |
| 6 | +示例： |
| 7 | +```python |
| 8 | +输入: 1 1 |
| 9 | + / \ / \ |
| 10 | + 2 3 2 3 |
| 11 | + |
| 12 | + [1,2,3], [1,2,3] |
| 13 | + |
| 14 | +输出: true |
| 15 | +``` |
| 16 | + |
| 17 | +#### 代码 |
| 18 | +递归</br> |
| 19 | +* 如果两个二叉树都为空，则两个二叉树相同 |
| 20 | +* 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同 |
| 21 | +* 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同 |
| 22 | +* 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同 |
| 23 | + |
| 24 | +```python |
| 25 | + |
| 26 | +class TreeNode: |
| 27 | + def __init__(self, val=0, left=None, right=None): |
| 28 | + self.val = val |
| 29 | + self.left = left |
| 30 | + self.right = right |
| 31 | + |
| 32 | + |
| 33 | +def isSameTree(p, q): |
| 34 | + if p is None and q is None: |
| 35 | + return True |
| 36 | + |
| 37 | + if p and q: |
| 38 | + if p.val == q.val: |
| 39 | + return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) |
| 40 | + else: |
| 41 | + return False |
| 42 | + |
| 43 | + return False |
| 44 | + |
| 45 | + |
| 46 | +if __name__ == '__main__': |
| 47 | + p = TreeNode(1) |
| 48 | + p.left = TreeNode(2) |
| 49 | + p.right = TreeNode(3) |
| 50 | + |
| 51 | + q = TreeNode(1) |
| 52 | + q.left = TreeNode(2) |
| 53 | + q.right = TreeNode(3) |
| 54 | + |
| 55 | + res = isSameTree(p, q) |
| 56 | + print(res) |
| 57 | +``` |
| 58 | + |
| 59 | +迭代</br> |
| 60 | +* 使用两个队列分别存储两个二叉树的节点 |
| 61 | +* 初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行比较操作 |
| 62 | +* 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同 |
| 63 | +* 如果两个节点的值相同，则判断两个节点的子节点是否为空,如果一个节点的左节点为空，另一个节点的子节点不为空，则两个二叉树的结构不同，因此两个二叉树一定不同 |
| 64 | +* 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列 |
| 65 | + |
| 66 | +```python |
| 67 | +from collections import deque |
| 68 | +def isSameTree(p, q): |
| 69 | + if p is None and q is None: |
| 70 | + # 根节点全为None |
| 71 | + return True |
| 72 | + |
| 73 | + if not p or not q: |
| 74 | + # 根节点一个为None,一个不为None |
| 75 | + return False |
| 76 | + |
| 77 | + queue1 = deque([p]) |
| 78 | + queue2 = deque([q]) |
| 79 | + |
| 80 | + while queue1 and queue2: |
| 81 | + node1 = queue1.popleft() |
| 82 | + node2 = queue2.popleft() |
| 83 | + # 比较两个节点的值 |
| 84 | + if node1.val != node2.val: |
| 85 | + return False |
| 86 | + left1 = node1.left |
| 87 | + right1 = node1.right |
| 88 | + left2 = node2.left |
| 89 | + right2 = node2.right |
| 90 | + |
| 91 | + # 比较两个子节点的结构，如果一个左子节点为None，另一个左子节点不为None，则返回False |
| 92 | + # 加not是因为 节点对象不能直接进行异或运算，需要转换成布尔对象再进行异或运算 |
| 93 | + if (not left1) ^ (not left2): |
| 94 | + return False |
| 95 | + if (not right1) ^ (not right2): |
| 96 | + return False |
| 97 | + if left1: |
| 98 | + queue1.append(left1) |
| 99 | + if right1: |
| 100 | + queue1.append(right1) |
| 101 | + if left2: |
| 102 | + queue2.append(left2) |
| 103 | + if right2: |
| 104 | + queue2.append(right2) |
| 105 | + # 如果两个树相同，最后两个队列都为空 |
| 106 | + return not queue1 and not queue2 |
| 107 | +``` |
0 commit comments