【LeetCode】101. Symmetric Binary Tree

题目

给你一个二叉树的根节点 root , 检查它是否轴对称.

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

题解

递归
Compare the left and right subtrees of the root subtree if they are symmetric

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    bool fun(TreeNode* node1,TreeNode* node2)
    {
    
        if(node1==nullptr && node2==nullptr)
            return true;
        if(!(node1 && node2))
            return false;
        if(node1->val != node2->val)
            return false;
        return (fun(node1->left,node2->right)&&fun(node1->right,node2->left));
    }
    bool isSymmetric(TreeNode* root) {
    
        if(root==nullptr)
            return false;
        return fun(root->left,root->right);
    }
};

迭代

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    bool isSymmetric(TreeNode* root) {
    
        if(root==nullptr)
            return false;
        
        queue<TreeNode*> myqueue1,myqueue2;
        myqueue1.emplace(root->left);
        myqueue2.emplace(root->right);

        while(!myqueue1.empty() && !myqueue1.empty())
        {
    
            TreeNode* node1 = myqueue1.front();
            TreeNode* node2 = myqueue2.front();
            myqueue1.pop();
            myqueue2.pop();
            if(!node1 && !node2)
                continue;
            if((!node1 || !node2) || node1->val != node2->val)
                return false;
            myqueue1.emplace(node1->left);
            myqueue1.emplace(node1->right);
            myqueue2.emplace(node2->right);
            myqueue2.emplace(node2->left);
        }
        return true;
    }
};