Leetcode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note: Bonus points if you could solve it both recursively and iteratively.
귀속 방법의 관건은 두 개의 나무로 나눌 생각을 하는 것이다.

/**
 * Definition for binary tree
 * 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 == NULL) {
            return true;
        }
        
        return checkSymmetric(root->left, root->right);
    }
    
    bool checkSymmetric(TreeNode *left, TreeNode *right) {
        if (left == NULL && right == NULL) {
            return true;
        }
        else if (left == NULL || right == NULL) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        
        return (checkSymmetric(left->left, right->right) && 
                checkSymmetric(left->right, right->left));
    }
};

비귀속 방법은 차원에 따라 두루 훑어볼 수 있다.

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

};

중서가 빗나가지만 첫 번째 반응은 생각한 것이다.
===================== 두 번째 =============================
귀속, 비교적 간단:

/**
 * Definition for binary tree
 * 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 == NULL) {
            return true;
        }
        
        return isMirror(root->left, root->right);
    }
    
    bool isMirror(TreeNode *left, TreeNode *right)  {
        if (left == NULL && right == NULL) {
            return true;
        }
        else if (left == NULL || right == NULL) {
            return false;
        }
        
        return (left->val == right->val
                && isMirror(left->left, right->right) 
                && isMirror(left->right, right->left));
    }
};

역귀적이지 않으면 중차 역행이 틀릴 뿐만 아니라 전차 역행+후속 역행도 문제를 해결할 수 없다. - 그 원인을 따지자면 어떤 단일 역행 알고리즘이 유일하게 나무를 확정할 수 없기 때문이다.그럼, 쓰고 놀 권리, 전서+중서+후속, 드디어 됐어요.

/**
 * Definition for binary tree
 * 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 == NULL) {
            return true;
        }
        
        vector<int> left = preorderTraversal(root->left);
        vector<int> right = postorderTraversal(root->right);
        if (left.size() != right.size()) {
            return false;
        }
        
        int size = left.size();
        for (int i = 0; i < size; ++i) {
            if (left[i] != right[size-i-1]) {
                return false;
            }
        }
        
        vector<int> inorder = inorderTraversal(root);
        for (int i = 0; i < size; ++i) {
            if (inorder[i] != inorder[2*size-i]) {
                return false;
            }
        }
        
        return true;
    }
    
    vector<int> preorderTraversal(TreeNode *root) {  
        vector<int> result;  
        stack<TreeNode*> nodes;  
        while (root != NULL || !nodes.empty()) {  
            while (root != NULL) {  
                result.push_back(root->val);  
                nodes.push(root);  
                root = root->left;  
            }  
              
            if (!nodes.empty()) {  
                root = nodes.top();  
                nodes.pop();  
                root = root->right;  
            }  
        }  
          
        return result;  
    }  
    
    vector<int> postorderTraversal(TreeNode *root) {  
        vector<int> result;  
        stack<TreeNode*> nodes;  
        TreeNode *prev = NULL;  
        while (root != NULL || !nodes.empty()) {  
            while (root != NULL) {  
                nodes.push(root);  
                root = root->left;  
            }  
              
            if (!nodes.empty()) {  
                root = nodes.top();  
                if (root->right == NULL || root->right == prev) {  
                    result.push_back(root->val);  
                    nodes.pop();  
                    prev = root;  
                    root = NULL;  
                }  
                else {  
                    root = root->right;  
                }  
            }  
        }  
          
        return result;  
    } 
    
    vector<int> inorderTraversal(TreeNode *root) {  
        vector<int> result;  
        stack<TreeNode*> nodes;  
        while (root != NULL || !nodes.empty()) {  
            while (root != NULL) {  
                nodes.push(root);  
                root = root->left;  
            }  
              
            if (!nodes.empty()) {  
                root = nodes.top();  
                nodes.pop();  
                result.push_back(root->val);  
                root = root->right;  
            }  
        }  
          
        return result;  
    }  
};