[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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 }

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄