leetcode/100. Same Tree.java at master · yusiftaghiyev/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// Version One: Recursive
public class Solution{
	public boolean is isSameTree(TreeNode p, TreeNode q){
		// Corner cases
		if(p == null && q == null){
			return true;
		}else if(p == null || q == null){
			return false;
		}

		return ((p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
	}
}

// Version Two: Iterative
public class Solution{
	public boolean isSameTree(TreeNode p, TreeNode q){
		Queue<TreeNode> q1 = new LinkedList<TreeNode>();
		Queue<TreeNode> q2 = new LinkedList<TreeNode>();

		q1.offer(p);
		q2.offer(q);

		while(!q1.isEmpty() && !q2.isEmpty()){
			TreeNode x = q1.poll();
			TreeNode y = q2.poll();

			if(((x == null) && (y != null)) || ((x != null) && (y == null))) return false;

			if(x.val != y.val) return false;

			q1.offer(x.left);
			q1.offer(x.right);
			q2.offer(y.left);
			q2.offer(y.right);
		}

		return true;
	}
}