对称二叉树---leetcode 101题

 解法1：递归法

class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right) {
        if(left == NULL && right != NULL) return false;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right == NULL) return true;
        else if(left->val != right->val) return false;

        bool outside = compare(left->left,right->right);
        bool inside = compare(left->right,right->left);
        bool isSame = outside && inside;
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left,root->right);
    }
};

解法2：迭代法，使用队列

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        queue que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            TreeNode* leftnode = que.front();
            que.pop();
            TreeNode* rightnode = que.front();
            que.pop();
            if(!leftnode && !rightnode){
                continue;
            }
            if((!leftnode || !rightnode || (leftnode->val != rightnode->val))){
                return false;
            }
            que.push(leftnode->left);
            que.push(rightnode->right);
            que.push(leftnode->right);
            que.push(rightnode->left);
        }
        return true;
    }
};

 解法3：迭代法，使用栈

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        stack st;
        st.push(root->left);
        st.push(root->right);
        while(!st.empty()){
            TreeNode* leftnode = st.top();
            st.pop();
            TreeNode* rightnode = st.top();
            st.pop();
            if(!leftnode && !rightnode){
                continue;
            }
            if((!leftnode || !rightnode || (leftnode->val != rightnode->val))){
                return false;
            }
            st.push(leftnode->left);
            st.push(rightnode->right);
            st.push(leftnode->right);
            st.push(rightnode->left);
        }
        return true;
    }
};