[leetcode]100. Same Tree相同的树

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

题意：

给定两个树，判断两个数是否相同

Solution1： DFS (Code will be neat and simple)

code

 1 class Solution {
 2     public boolean isSameTree(TreeNode p, TreeNode q) {
 3         if(p ==null && q ==null) return true;
 4         if(p ==null || q ==null) return false;  
 5         
 6         if(p.val == q.val){
 7              return  isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
 8         }
 9         return false;   
10     }
11 }

Solution2： Iteration(Using a stack or a queue to simulate how DFS works)

code

 1 class Solution {
 2     public boolean isSameTree(TreeNode p, TreeNode q) {
 3         Queue<TreeNode> queue = new LinkedList<>();
 4         
 5         queue.add(p);
 6         queue.add(q);
 7         
 8         while(!queue.isEmpty()){
 9             TreeNode node1 = queue.remove();
10             TreeNode node2 = queue.remove();      
11             
12             if(node1==null && node2 ==null) continue;
13             if(node1==null || node2==null) return false;
14             if(node1.val != node2.val)  return false;
15             
16             queue.add(node1.left);
17             queue.add(node2.left);
18             
19             queue.add(node1.right);
20             queue.add(node2.right);
21         }
22         return true;
23     }
24 }