101.Symmetric Tree

101.Symmetric Tree

难度:Easy

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

递归： 通过一个函数判断，左子树的右孩子和右子树的左孩子，左子树的左孩子和右子树的右孩子应该相等。

/**
 * 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 {
bool check(TreeNode* left , TreeNode* right)
{

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

执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.7MB, 在所有 C++ 提交中击败了88.35%的用户

迭代： 创建一个队列来保存二叉树的每个节点，然后比较左节点的右孩子和右节点的左孩子。

/**
 * 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;
        if(!root->left && !root->right) return true;
        deque<TreeNode*> t;
        t.push_back(root);
        t.push_back(root);
        while(!t.empty())
        {
            if(!t[0] &&!t[1]) 
            {
                t.pop_front();
                t.pop_front();
                continue;
            }
            if(!t[0] || !t[1]) return false;
            if(t[0]->val != t[1]->val) return false;
            t.push_back(t[0]->left);
            t.push_back(t[1]->right);
            t.push_back(t[0]->right);
            t.push_back(t[1]->left);
            t.pop_front();
            t.pop_front();
        }
        return true;
        
    }
};

执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户 内存消耗 :14.9MB, 在所有 C++ 提交中击败了79.96%的用户