LeetCode(101)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
제목 분석:
이 문제의 귀속 해답은 비교적 생각해 보니, 그림을 보고 코드를 쓰면 된다.비귀속 해답은 제가 시간이 많이 걸려서 했습니다. 처음에queue+stack의 방식으로 하나하나 스캔을 시도했고 흥분해서 간결한 방법을 생각해 봤는데 틀렸어요. 제목에서 언급한 반례도 해결할 수 없었어요.그래서 숫자 크기의 대칭이 필요할 뿐만 아니라 좌우의 대칭이 필요하다는 것을 알아차렸다. 예를 들어 위의 반례 중의 세 번째 줄 3과 3, 숫자는 대칭이지만 좌우는 비대칭이다.그래서 다시 고쳐서 다시 제출하고 몇 번 시험해 봤는데 드디어 끝났어요.
내 귀속 버전 코드는 다음과 같다

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

내 비귀속 버전은 다음과 같습니다.

//  44ms  
class Solution {
public:
        bool isSymmetric(TreeNode *root) {
        stack<TreeNode*> node_stack;
        vector<TreeNode*> node_vector;
        queue< vector<TreeNode*> > large_node_queue;
        if((root==NULL)||(root!=NULL&&root->left==NULL&&root->right==NULL))
            return true;
        if((root->left!=NULL&&root->right==NULL)||(root->left==NULL&&root->right!=NULL))
            return false;
        node_vector.push_back(root->left);
        node_vector.push_back(root->right);
        large_node_queue.push(node_vector);
        while(!large_node_queue.empty()) {
            node_vector=large_node_queue.front();
            large_node_queue.pop();
            vector<TreeNode*> node_vector2;
            int i=0;
            int j=(int)node_vector.size()-1;
            while(i<j){
                if( (node_vector[i]==NULL&&node_vector[j]!=NULL) || (node_vector[i]!=NULL&&node_vector[j]==NULL) )
                    return false;
                if(node_vector[i]!=NULL&&node_vector[j]!=NULL&&node_vector[i]->val!=node_vector[j]->val)
                    return false;
                i++;
                j--;
            }
            for(i=0;i<(int)node_vector.size();i++){
                    if(node_vector[i]!=NULL){
                        node_vector2.push_back(node_vector[i]->left);
                        node_vector2.push_back(node_vector[i]->right);
                    }
            }
            if(!node_vector2.empty())
                large_node_queue.push(node_vector2);
        }
        return true;
    }
};

소결:
(1) 코드를 쓰는 시간이 짧으려면 논리적 구조와 경계 조건을 분명히 생각하고 써야 한다는 것을 점점 발견하고 있다.다 썼는데도 정례와 반례를 측정하는 것을 잊지 마라.만약 debug에 의존해서 코드를 다 쓰고 싶다면, 그것은 매우 시간이 걸릴 것이다.면접뿐만 아니라 업무 효율을 높이기 위해서다.
업데이트 2014-10-09 귀속판이 더 간결하게 바뀌었어요.

class Solution {
private:
    bool mySymmetric(TreeNode* left_node, TreeNode* right_node) {
        if (left_node != NULL && right_node != NULL && left_node->val == right_node->val)
            return mySymmetric(left_node->left, right_node->right) &&
                    mySymmetric(left_node->right, right_node->left);
        else if (left_node == NULL && right_node == NULL)
            return true;
        else 
            return false;
    }
public:
    bool isSymmetric(TreeNode *root) {
        if (root == NULL) return true;
        return mySymmetric(root->left, root->right);
    }
};

업데이트 2014-10-09 비귀속판도 더 간결하게 고쳤어요.

class Solution {
public:
        bool isSymmetric(TreeNode *root) {
        vector<TreeNode*> node_vector;
        if (root == NULL)
            return true;
        node_vector.push_back(root->left);
        node_vector.push_back(root->right);
        while (!node_vector.empty()) {
            vector<TreeNode*> node_vector_tmp;
            int i=0;
            int j=(int)node_vector.size() - 1;
            while (i < j) {
                if( (node_vector[i] == NULL && node_vector[j] != NULL) || (node_vector[i] != NULL && node_vector[j] == NULL) )
                    return false;
                if(node_vector[i] != NULL && node_vector[j] != NULL && node_vector[i]->val != node_vector[j]->val)
                    return false;
                ++i;
                --j;
            }
            for (i = 0; i < (int)node_vector.size(); ++i){
                if(node_vector[i]!=NULL){
                    node_vector_tmp.push_back(node_vector[i]->left);
                    node_vector_tmp.push_back(node_vector[i]->right);
                }
            }
            node_vector.swap(node_vector_tmp);
        }
        return true;
    }
};