E
tags: Tree, DFS, BFS
time: O(n)
space: O(logn)
给两个 binary tree, 看两个tree是否identical.
#### Method1: DFS
- DFS. 确定leaf条件, && with all dfs(sub1, sub2).
- 这里无论如何都要走过所有的node, 所以dfs更加合适, 好写.
#### Method2: BFS with 2 queues
- 两个queue存每个tree的所有current level node. Check equality, check queue size.
- Populate next level by nodes at current level.
```
/*
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical
and the nodes have the same value.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
Method1: DFS
Use the function itself with dfs.
Check p == q, p.left==q.left, p.right==q.right
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) return p == null && q == null;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
// Method2: BFS
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue pp = new LinkedList<>();
Queue qq = new LinkedList<>();
pp.offer(p);
qq.offer(q);
while (!pp.isEmpty() && !qq.isEmpty()) {
p = pp.poll();
q = qq.poll();
if (p == null && q == null) continue;
if (p == null ^ q == null) return false;
if (p.val != q.val) return false;
offer(p, pp);
offer(q, qq);
}
return true;
}
private void offer(TreeNode node, Queue queue) {
queue.offer(node.left);
queue.offer(node.right);
}
}
```