Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to judge the symmetry tree by C++". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Judge symmetric tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

one

/

2 2

/ /

3 4 4 3

But the following is not:

one

/

2 2

3 3

Note:

Bonus points if you could solve it both recursively and iteratively.

To judge whether a binary tree is a balanced tree, for example, there are two nodes N1 and N2, we need to compare whether the values of the left child node of N1 and the right child node of N2 are equal. At the same time, we also compare whether the values of the right child node of N1 and the left child node of N2 are equal, and so on. We can use recursive and iterative methods to achieve it, the writing method is different, but the core of the algorithm is the same.

Solution 1:

Class Solution {public: bool isSymmetric (TreeNode * root) {if (! root) return true; return isSymmetric (root- > left, root- > right);} bool isSymmetric (TreeNode * left, TreeNode * right) {if (! left & &! right) return true; if (left & & right | |! left & & right | | left- > val! = right- > val) return false Return isSymmetric (left- > left, right- > right) & & isSymmetric (left- > right, right- > left);}}

Iterative writing needs to be implemented with two queues of queue. We first decide to be null, and if root is empty, we directly return true. Otherwise, the left and right child nodes of the root are loaded into two queues respectively, and then the loop starts on the condition that neither queue is empty. In the while loop, we first extract the first element of the queue from the two queues. If both are empty nodes, then skip them directly. Because we have not finished the comparison, it is possible that a node does not have a left child node, but the right child node still exists, so there is only continue here. And then look, if one is empty and the other is not empty, then the symmetry has been broken, so you don't have to compare it any more, just return to false. If both nodes exist, but their node values are different, it also breaks the symmetry and returns false. Otherwise, put the left child node and right child node of node1 into queue 1, note that the right child node and left child node of node2 should be placed in queue 2, and pay attention to the corresponding problem of sequence. Return true directly after the end of the loop. There is no need to check whether the two queues are empty at the same time, because it is only possible that both queues are empty at the end of the loop. In other cases, if both queues are empty, return false directly inside the loop, as shown in the code below:

Solution 2:

Class Solution {public: bool isSymmetric (TreeNode* root) {if (! root) return true; queue Q1, Q2; q1.push (root- > left); q2.push (root- > right); while (! q1.empty () &! q2.empty ()) {TreeNode* node1 = q1.front (); q1.pop (); TreeNode* node2 = q2.front (); q2.pop () If (! node1 & &! node2) continue; if ((node1 &! node2) | | (! node1 & & node2)) return false; if (node1- > val! = node2- > val) return false; q1.push (node1- > left); q1.push (node1- > right); q2.push (node2- > right); q2.push (node2- > left) } return true;}}; "how C++ judges the symmetric Tree" ends here. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.