leetcode100. 相同的树

**相同的树**

给定两个根节点为 `root1` 和 `root2` 的二叉树，判断这两棵树是否相同。

**示例1:**

输入：`root1 = [3,9,20,null,null,15,7], root2 = [3,9,20,null,null,15,7]`
输出：`true`

**示例2:**

输入：`root1 = [3,5,1,6,0,9,2,null,4], root2 = [3,5,1,6,0,9,2,null,4]`
输出：`true`

**示例3:**

输入：`root1 = [3,5,1,6,0,9,2,null,4], root2 = [3,5,1,6,0,9,7]`
输出：`false`

**解决方案**

我们可以使用递归的方式来判断这两棵树是否相同。具体来说，我们可以定义一个函数 `isSameTree(root1, root2)`，这个函数会返回一个布尔值，表示这两棵树是否相同。

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isSameTree(root1, root2):
 # 如果两个树都为空，则它们是相同的 if not root1 and not root2:
 return True # 如果一个树为空，而另一个树不为空，则它们是不相同的 if not root1 or not root2:
 return False # 如果两个树的值不同，则它们是不相同的 if root1.val != root2.val:
 return False # 递归检查左子树和右子树是否相同 return isSameTree(root1.left, root2.left) and isSameTree(root1.right, root2.right)

# 测试用例1root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)

root2 = TreeNode(3)
root2.left = TreeNode(9)
root2.right = TreeNode(20)
root2.right.left = TreeNode(15)
root2.right.right = TreeNode(7)

print(isSameTree(root1, root2)) # 输出：True# 测试用例2root1 = TreeNode(3)
root1.left = TreeNode(5)
root1.right = TreeNode(1)
root1.right.left = TreeNode(6)
root1.right.right = TreeNode(0)
root1.right.right.right = TreeNode(9)
root1.right.right.right.right = TreeNode(2)

root2 = TreeNode(3)
root2.left = TreeNode(5)
root2.right = TreeNode(1)
root2.right.left = TreeNode(6)
root2.right.right = TreeNode(0)
root2.right.right.right = TreeNode(9)
root2.right.right.right.right = TreeNode(2)

print(isSameTree(root1, root2)) # 输出：True# 测试用例3root1 = TreeNode(3)
root1.left = TreeNode(5)
root1.right = TreeNode(1)
root1.right.left = TreeNode(6)
root1.right.right = TreeNode(0)
root1.right.right.right = TreeNode(9)
root1.right.right.right.right = TreeNode(2)

root2 = TreeNode(3)
root2.left = TreeNode(5)
root2.right = TreeNode(1)
root2.right.left = TreeNode(6)
root2.right.right = TreeNode(0)
root2.right.right.right = TreeNode(9)
root2.right.right.right.right = TreeNode(7)

print(isSameTree(root1, root2)) # 输出：False