Simple Iterative Solution with BFS(Queue)


  • 0
    C
    public class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p == null && q == null) return true;
            if(p == null || q == null)return false;
            Queue<TreeNode> p1 = new LinkedList<TreeNode>();
            Queue<TreeNode> q1 = new LinkedList<TreeNode>();
    // Insert both the roots into the queue
            p1.offer(p);
            q1.offer(q);
            while(!q1.isEmpty() && !p1.isEmpty()){
    // Take out both the elements at the front of the queue and 
    //check if the values are same. If not return false 
                p = p1.poll();
                q = q1.poll();
                if(p.val == q.val){
    // Check if both nodes have left child. if not return false
                    if(p.left != null && q.left != null){
                        p1.offer(p.left);
                        q1.offer(q.left);
                    }
    // Here OR condition is added in else. Consider example p = [0]
    // & q = [0]. If you simply write else, it will return false. Hence
    // If condition is added to check If one of them is null, return false
                   
     else if(p.left != null || q.left != null){
                        return false;
                    }
    // Similar for right child
    
                    if(p.right != null && q.right != null){
                        p1.offer(p.right);
                        q1.offer(q.right);
                    }
                    else if(p.right != null || q.right != null){
                        return false;
                    }
                }
                else{
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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