[JAVA]BFS solution for Same Tree


  • 0
    G

    The benefit for using iterate rather than recursion is you won't easy get Stack overflow.

    public class solution{
     public boolean isSameTree(TreeNode p, TreeNode q) {
            Queue<TreeNode> p1 = new LinkedList<TreeNode>();
            Queue<TreeNode> p2 = new LinkedList<TreeNode>();
            if(p==null&&q==null)return true;
            if(p==null||q==null)return false;
            p1.offer(p);
            p2.offer(q);
            while(!p1.isEmpty()&&!p2.isEmpty()){
                int cnt1 = p1.size();
                int cnt2 = p2.size();
                if(cnt1!=cnt2)return false;
                for(int i=0;i<Math.max(cnt1,cnt2);i++){
                    TreeNode curr1=p1.poll();
                    TreeNode curr2= p2.poll();
                    if(curr1.val!=curr2.val)return false;
                   
                    if(curr1.left!=null)p1.offer(curr1.left);
                    if(curr2.left!=null)p2.offer(curr2.left);
                     if(p1.size()!=p2.size())return false;
                    
                    if(curr1.right!=null)p1.offer(curr1.right);
                    if(curr2.right!=null)p2.offer(curr2.right);
                     if(p1.size()!=p2.size())return false;
                    
                }
            }
            if(p1.size()!=0||p2.size()!=0)return false;
            
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.