qiaoxu123
1/7/2019 - 12:51 AM

101. Symmetric Tree

对称二叉树的判断 进一步考察对二叉树的了解，方法有递归形式和非递归形式

  • Approach 1 ： recursive

改变递归遍历的次序，从而进行对称的比较

  • Approach 2 ： queue

使用队列进行存储，进行宽度优先比较

recursive.cpp
content_copyfile_download
//Runtime: 8 ms, faster than 39.55%

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return travelTree(root->left,root->right);
    }
    
    bool travelTree(TreeNode* p,TreeNode* q){
        if(!p && !q) 
            return true;
        else if(!p || !q)
            return false;
        if(p->val != q->val)
            return false;
        return travelTree(p->left,q->right) && travelTree(p->right,q->left);
    }
};
queue.cpp
content_copyfile_download
//Runtime: 8 ms, faster than 39.55%

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