검지offer-서열화 두 갈래 나무

문제.

제목: [검지offer-서열화된 두 갈래 나무]

사고의 방향

먼저 말하자면, 아래의 코드는 없었지만, 사고방식은 옳았다.나는 서열이 반드시 완전한 두 갈래 나무의 형식을 제시해야만 내가 정확한 다음 표를 계산할 수 있다고 요구한다.하지만 제목을 서열화할 때는 이렇게 주지 않는다.나는 몇몇 인터넷 방법을 참고했는데, 모두가 서열화라는 물건에 대해 모두 자신의 정의를 가지고 있다.
본질은 완전 두 갈래 나무 서열에 따라 구축한 다음에 넓이를 우선적으로 훑어보는 것이다.

코드

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(!root) return NULL;
        string ret;

        ret += (char)('0'+root->val);
        queue que;
        que.push(root);

        while(!que.empty()){
            root = que.front();
            que.pop();

            if( root->left ){
                ret += (char)('0'+root->left->val);
                que.push(root->left);
            }
            else
                ret += '#';

            if(root->right){
                ret += (char)('0'+root->right->val);
                que.push(root->right);
            }
            else
                ret += '#';
        }
        int sz = ret.size();
        int idx = sz - 1;
        while(ret[idx]=='#') --idx;
        string tmp = ret.substr(0, idx+1);
        return const_cast<char*>(tmp.c_str());

    }
    TreeNode* Deserialize(char *str) {
        if(!str) return NULL;
        return create_bitree( str, 0, strlen(str)-1 );
    }
private:
    TreeNode* create_bitree(char* str, int cur, int n){
        if( cur > n ) return NULL;
        if( str[cur] == '#' ) return NULL;

        TreeNode* root = new TreeNode( str[cur] - '0' );
        root->left = create_bitree( str, cur*2+1, n );
        root->right = create_bitree( str, cur*2 + 2, n );

        return root;
    }
};

생각 2

오늘 이 문제를 다시 풀었는데도 여전히 풀리지 않았다.어제 말미에 나는 사람들이 서열화된 서열에 대해 서로 다른 정의를 가지고 있기 때문에 다른 방법을 만들었을 것이라고 생각했다.오늘 나는 먼저 순서를 두루 훑어보는 방법을 채택하여 서열화를 만들었다.왼쪽 트리가 비어 있지만 오른쪽 트리가 비어 있지 않을 경우 # 추가

코드

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string ans;
        pre_order( root, ans );

        return const_cast<char*>( ans.c_str() );
        //return ans;
    }
    TreeNode* Deserialize(char *str) {
        if( !str ) return NULL;
        int cur = 0;
        int n = strlen(str);

        return create_bitree( str, cur, n );
    }
private:
    TreeNode* create_bitree(char* arr, int& cur, int n){
        if( cur >= n || arr[cur] == '#' ) return NULL;
        else{
            TreeNode* root = new TreeNode( arr[cur] ); ++cur;
            root->left = create_bitree( arr, cur, n );
            root->right = create_bitree( arr, cur, n  );
            return root;
        }
    }
    int pre_order(TreeNode* root, string& ans){
        if(!root) return -1;
        else{
            ans += static_cast<char>(root->val);

            int ret = pre_order( root->left, ans );
            if(-1==ret && root->right){
                ret+='#';
            }

            pre_order( root->right, ans );


            return 0;
        }
    }
};

이것은 지나친 링크입니다 [검지offer 서열화 두 갈래 나무]