BFS iterative solution


  • 0
    H
        public boolean isSameTree(TreeNode p, TreeNode q) {
            // iterative BFS traversal
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(p);
            queue.add(q);
            // loop invariant: compare after dequeue
            while(!queue.isEmpty()){
                // let's say left tree and right tree
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                if(left==null && right==null) continue;
                if(left==null ^ right==null) return false;
                if(left.val != right.val) return false;
                // enqueue corresponding positions by pairs in the queue
                queue.add(left.left);
                queue.add(right.left);
                queue.add(left.right);
                queue.add(right.right);
            }
            return true;
        }
    

Log in to reply
 

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