力扣-101题对称二叉树（C++）- 递归+迭代

秒速五厘米 2022-08-31 11:25 168阅读 0赞

题目链接：[https://leetcode-cn.com/problems/symmetric-tree/][https_leetcode-cn.com_problems_symmetric-tree]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
解法一：递归

/**
     * 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) {
        
            //注：要判断的是两个子树是否是对称的，所以递归的参数为左右子树
            //    返回的值是bool类型
            if(root==NULL) return true;
            //if((root->left==NULL&&root->right!=NULL)||((root->left!=NULL&&root->right==NULL))) return false;
    
            return dfs(root->left,root->right);
        }
    
        bool dfs(TreeNode* left,TreeNode* right){
        
            //终止条件为：两个节点是否为空，以及数值是否相同
            if(left==NULL&&right==NULL) return true;
            if(left!=NULL&&right==NULL) return false;
            if(left==NULL&&right!=NULL) return false;
    
            if(left->val!=right->val) return false;
    
            return dfs(left->left,right->right)&&dfs(left->right,right->left);
    
        }
    };

解法二：迭代

/**
     * 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==NULL) return true;
    
            queue<TreeNode*> que;
            que.push(root->left);
            que.push(root->right);
    
            while(!que.empty()){
        
                TreeNode* left=que.front();que.pop();
                TreeNode* right=que.front();que.pop();
    
                if(left==NULL&&right==NULL) continue;
    
                if(left==NULL&&right!=NULL) return false;
                if(left!=NULL&&right==NULL) return false;
                if(left->val!=right->val) return false;
    
                que.push(left->left);
                que.push(right->right);
                que.push(left->right);
                que.push(right->left);
            }
    
            return true;
        }
    };

[https_leetcode-cn.com_problems_symmetric-tree]: https://leetcode-cn.com/problems/symmetric-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/33b5a83bc8ec47a2837c5afd674d5754.png