Leetcode 100 Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution 1: DFS, recursive

 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     return dfs(p,q);  
   }  
   private boolean dfs(TreeNode x, TreeNode y) {  
     if (x==null && y==null) return true;  
     if (x==null || y==null) return false;  
     if (x.val != y.val) return false;  
     return dfs(x.left, y.left) && dfs(x.right, y.right);  
   }  
 }  

Solution 1: DFS, iterative

 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     Deque<TreeNode> s1=new LinkedList<>();  
     Deque<TreeNode> s2=new LinkedList<>();  
     TreeNode x=p, y=q;  
     if (x==null && y!=null) return false; //corner case  
     while (x!=null || !s1.isEmpty()) {  
       if (x!=null) {  
         if (y==null) return false;  
         s1.push(x);  
         s2.push(y);  
         x=x.left;  
         y=y.left;  
       }  
       else {  
         if (y!=null) return false;  
         x=s1.pop();  
         y=s2.pop();  
         if (x.val!=y.val) return false;  
         x=x.right;  
         y=y.right;  
       }  
     }  
     return true;  
   }  
 }