101. Symmetric Tree

我会带着你远行 2022-05-11 18:46 101阅读 0赞

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

For example, this binary tree `[1,2,2,3,4,4,3]` is symmetric:

1
       / \
      2   2
     / \ / \
    3  4 4  3

But the following `[1,2,2,null,3,null,3]` is not:

1
       / \
      2   2
       \   \
       3    3

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

方法1：递归

方法2：非递归

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