[Lc]面试题28对称的二叉树

题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

这道题三种解法，递归，栈迭代（先序遍历），队列迭代（层次遍历）。与101题一模一样，具体注释就看101题就行，这里再记录练习写的代码

1. 递归法

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    bool helper(TreeNode* p, TreeNode* q){
        if(!p && !q) return true;
        if(!p || !q) return false;
        if(p->val != q->val) return false;
        return helper(p->left, q->right) && helper(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {//三种方法 1.递归
        if(!root) return true;
        return helper(root->left, root->right);
    }
};

2. 栈迭代法

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        stack<TreeNode*> sL;
        stack<TreeNode*> sR;
        TreeNode* curLeft = root->left;
        TreeNode* curRight = root->right;
        while(curLeft || !sL.empty() || curRight || !sR.empty()){
            while(curLeft){
                sL.push(curLeft);
                curLeft = curLeft->left;
            }
            while(curRight){
                sR.push(curRight);
                curRight = curRight->right;
            }
            if(sL.size() != sR.size()) return false;
            curLeft = sL.top();sL.pop();
            curRight = sR.top();sR.pop();
            if(curLeft->val != curRight->val) return false;
            curLeft = curLeft->right;
            curRight = curRight->left;
        }
        return true;
    }

3. 队列迭代法

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(root->left);
        q2.push(root->right);
        while(!q1.empty() || !q2.empty()){
            auto curLeft = q1.front();q1.pop();
            auto curRight = q2.front();q2.pop();
            if(!curLeft && !curRight) continue;
            if(!curLeft || !curRight) return false;
            if(curLeft->val != curRight->val) return false;
            q1.push(curLeft->left);
            q1.push(curLeft->right);
            q2.push(curRight->right);
            q2.push(curRight->left);
        }
        return true;
    }
};