https://leetcode.com/problems/symmetric-tree/

tree 가 대칭인지 여부

recursive

bool recursiveSymmetric(TreeNode* node1, TreeNode* node2){
    if(node1 && node2){ // 노드가 둘 다 있다면 다음 단계를 진행한다.
        if(node1->val != node2->val) return false;
        bool condi1 = recursiveSymmetric(node1->right, node2->left);
        bool condi2 = recursiveSymmetric(node1->left, node2->right);
        condi1 = condi1 && condi2;
        return condi1;
    }else if(node1 == NULL && node2 == NULL){ // 대칭되는 부분이 둘 다 없으면 똑같은거니까
        return true;
    }
    return false; // 한쪽이 null 이라면 대칭이 아니니까
}

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return false;
        return recursiveSymmetric(root->left, root->right);
    }
};

iterative

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return false;
        if(root->right == NULL && root->left == NULL) return true;
        
        stack<TreeNode*> curStack;
        stack<TreeNode*> mirrorStack;
        curStack.push(root->left);
        mirrorStack.push(root->right);
        
        while(!curStack.empty()){
            TreeNode* curNode = curStack.top();
            TreeNode* mirrorNode = mirrorStack.top();
            curStack.pop();
            mirrorStack.pop();
            
            if(curNode == NULL && mirrorNode == NULL) continue;
            else if(curNode && mirrorNode){
                if(curNode->val != mirrorNode->val) return false;
                curStack.push(curNode->left);
                mirrorStack.push(mirrorNode->right);
                curStack.push(curNode->right);
                mirrorStack.push(mirrorNode->left);
            }
            else return false;
        }
        return true;
    }
};