Topic describes

Train of thought

If a binary tree is symmetric, the root nodes of the left and right subtrees have equal values, and the left subtree of the left subtree is symmetric with the right subtree of the right subtree, and the right subtree of the left subtree is symmetric with the left subtree of the right subtree

The recursive implementation

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * /
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(! root) {return true;
        }
        return mirror(root->left, root->right);
    }
    
    // Add a function to compare left and right subtrees
    bool mirror(TreeNode* left, TreeNode* right) {
        if(! left && ! right) {return true;
        }
        if(! left || ! right) {return false;
        }
        return(left->val == right->val) && mirror(left->left, right->right) && mirror(left->right, right->left); }};Copy the code

Iteration implement

The structure of binary tree is very suitable to be realized by using the structure of stack. By putting the relevant nodes of the left and right subtrees into the stack, taking them out and then putting them into the subtree of a deeper layer until the stack is empty and the binary tree comes to an end. The implementation is as follows:

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(! root) {return true;
        }
        stack<TreeNode*> node_stack;
        TreeNode* p = NULL, *q = NULL;
        node_stack.push(root->left);
        node_stack.push(root->right);
        while(! node_stack.empty()) { p = node_stack.top(); node_stack.pop(); q = node_stack.top(); node_stack.pop(); // The two nodes are empty, continue traversalif(! p && ! q)continue; // The two nodes are not empty and the other is not emptyfalse
            if(! p || ! q)return false; // The value of the two nodes is not empty, obviously asymmetric, returnfalse
            if(p->val ! = q->val)return false; // The left subtree of the left subtree corresponds to the right subtree of the right subtree, and the right subtree of the left subtree corresponds to the left subtree of the right subtree. node_stack.push(q->right); node_stack.push(p->right); node_stack.push(q->left); }return true; }};Copy the code