LeetCode485: given two binary trees, write a function to check whether they are the same.

If two trees are structurally identical and the nodes have the same value, they are considered to be the same.

For example:

1. Recursive solution

It seems that two binary trees perform preorder traversal at the same time. First judge whether the root nodes are the same. If they are the same, then judge whether the left and right child nodes are the same. In the process of judgment, as long as one is different, it will return false. If they are all the same, it will return true.

That's exactly what happened. Look at the code:

public boolean isSameTree(TreeNode p, TreeNode q) {
//If they are all empty, we think they are the same 
if(p==null&&q==null)
return true; 
//If one is empty and the other is not empty, it is obvious that it cannot be the same tree. Just return false directly 
if(p==null||q==null)
return false; 
//If the two nodes are not empty and equal, they cannot be the same tree, and return false directly 
if (p.val != q.val)
return false; /
/Go to this step to explain the node p and q Is exactly the same. We just need to compare their left and right child nodes 
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
 }

2. Non recursive solution

Non recursive solution can refer to BFS traversal of the tree, that is, width first search, also known as breadth first search. It is traversed layer by layer, as shown in the following figure:

BFS code of binary tree is as follows:

    public void bfsPrint(TreeNode tree) {
        if (tree == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);//It is equivalent to adding data to the end of the queue 
        while (!queue.isEmpty()) {
        //The poll method is equivalent to removing elements from the queue header 
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

He uses a queue. He keeps putting the nodes of each layer into the queue, then leaves the queue, and then puts the child nodes into the queue

For this problem, we can use two queues, one for the first tree node and the other for the second tree node.

1. Every time the elements of the two queues leave the queue at the same time, judge whether the two node values of the queue are the same after leaving the queue. If they are different, return false directly. If they are the same, go down.
2. Then judge whether all their left child nodes exist. If one exists and the other does not exist, it will directly return false. If both exist, it will be added to the queue
3. The right child node is the same as the left child node
4. Finally, judge whether the two queues are empty

Although the code is a little long, the principle is relatively simple. Let's look at the code below:

 public boolean isSameTree(TreeNode p, TreeNode q) {
        //If they are all empty, we think they are the same
        if (p == null && q == null)
            return true;
        //If one is empty and the other is not empty, it is obvious that it cannot be the same tree. Just return false directly
        if (p == null || q == null)
            return false;
        Queue<TreeNode> queueP = new LinkedList<>();
        Queue<TreeNode> queueQ = new LinkedList<>();
        //If both p and q nodes are not empty, they are added to the queue
        queueP.add(p);
        queueQ.add(q);
        while (!queueP.isEmpty() && !queueQ.isEmpty()) { //Separate teams
            TreeNode tempP = queueP.poll();
            TreeNode tempQ = queueQ.poll(); //If the values of the two nodes are different, false is returned directly
            if (tempP.val != tempQ.val) return false;
//If the corresponding left child node is not empty, it will be added to the queue if (tempp. Left! = null)
            queueP.add(tempP.left);
            if (tempQ.left != null)
                queueQ.add(tempQ.left); //Note that it is not directly judged whether one of the two left child nodes is empty / / not empty, but by the length of the queue. The queue length will be the same only when the two left child nodes / / are empty or not empty
            if (queueP.size() != queueQ.size())
                return false;
//The right child node is the same as above
            if (tempP.right != null)
                queueP.add(tempP.right);
            if (tempQ.right != null)
                queueQ.add(tempQ.right);
            if (queueP.size() != queueQ.size())
                return false;
        }
//Finally, judge whether the two queues are empty
        return queueP.isEmpty() && queueQ.isEmpty();
    }