首页 > 试题广场 >

二叉树的序列化

[编程题]二叉树的序列化

热度指数：8798 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

二叉树被记录成文件的过程叫做二叉树的序列化。序列化的方法有很多，这里我们采用括号序列的方法将其序列化，所谓括号序列指的是对于一个节点生成一个括号，括号内是其子树的括号序列，其中左儿子(若存在)的括号在前，右儿子(若存在)的括号在后。对于给定的树，请设计高效的算法，将其序列化。

给定一个树的根节点指针root，请返回一个字符串，代表其序列化后的括号序列。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

李长宇

string toSequence(TreeNode* root) {
        // write code here
        if(!root) return "";
        return "("+toSequence(root->left)+toSequence(root->right)+")";
    }

发表于 2016-03-31 11:05:01 回复(5)

C/C++

蓝魔4

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class TreeToSequence {
public:
    void tostring(TreeNode* root,string &res)
    {
        if(root)
        {
            res.push_back('(');
            tostring(root->left,res);
            //res.push_back('(');
            //res.push_back(')');
            tostring(root->right,res);
            res.push_back(')');
        }
    }
    string toSequence(TreeNode* root) {
       string res;
       tostring(root,res);
       return res;
    }
};

发表于 2017-06-19 09:43:21 回复(0)

OnePiece~~

class TreeToSequence {
public:
    string getAns(TreeNode *root){
        string temp;
        if(!root) return temp;
        string s1,s2;
        if(root->left)
           s1 = getAns(root->left);
        if(root->right)
           s2 =getAns(root->right);
        temp+='(';
        temp+=s1;
        temp+=s2;
        temp+=')';
        return temp;
        
    }
    string toSequence(TreeNode* root) {
         string ans;
         if(!root) return ans;
         ans=getAns(root);
         return ans;
    }
};

/*后序遍历*/

编辑于 2016-08-05 19:30:48 回复(0)

C++

勇敢牛牛，不怕困难！

class TreeToSequence {
public:
  string toSequence(TreeNode* root) {
    if (!root) return "";
    ostringstream s;
    s << '(';
    if (root->left)  s << toSequence(root->left);
    if (root->right) s << toSequence(root->right);
    s << ')';
    return s.str();
  }
};

发表于 2021-08-13 11:48:42 回复(0)

Python

TimeMac

格式化输出

class TreeToSequence:
    def toSequence(self, root):
        if root:
            return "(%s%s)" % (self.toSequence(root.left),self.toSequence(root.right))
        else:
            return ""

编辑于 2018-10-14 22:46:33 回复(0)

Angelべ天行

import java.util.*;

public class TreeNode {

int val = 0;

TreeNode left = null;

TreeNode right = null;

public TreeNode(int val) {

this.val = val;

}

}*/

public class TreeToSequence {

String str="";

public String toSequence(TreeNode root) {

// write code here

toSequence1 (root);

return str;

}

//递归，参数?

//递归的终止条件根节点是否为空

//递归状态先插入"("，然后左节点, 右节点最后")"

public void toSequence1 (TreeNode root) {

if(root==null){

return ;

}

str=str+"(";

toSequence1 ( root.left);

toSequence1 ( root.right);

str=str+")";

}

发表于 2018-03-29 13:33:16 回复(0)

Python

华科平凡

python solution

class TreeToSequence:
    def toSequence(self, root):
        if not root: return ""
        res = "("
        res += self.toSequence(root.left)
        res += self.toSequence(root.right)
        res += ")"
        return res

发表于 2017-11-07 18:17:29 回复(0)

C/C++

nbgao

class TreeToSequence {
public:
    string toSequence(TreeNode* root) {
        string result;
        Fun(root,result);
        return result;
    }
    void Fun(TreeNode *root, string &result){
        if(root)
        {             result.push_back('(');             Fun(root->left, result);             Fun(root->right, result);             result.push_back(')');         }     }
};

发表于 2017-10-12 01:33:58 回复(0)

sam146

    public String toSequence(TreeNode x) {
        if(x==null){
            return "";
        }
        return "("+toSequence(x.left)+toSequence(x.right)+")";
    }

发表于 2017-04-08 01:44:21 回复(0)

ForrestYuan

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreeToSequence {
    public String toSequence(TreeNode root) {
        // write code here
       	String str="";
        if(root==null){
            return "";
        }else{
            str="(";
            str+=toSequence(root.left);
            str+=toSequence(root.right);
            str+=")";
            return str;
        }
    }
}

发表于 2016-04-16 18:08:15 回复(3)

魔路锋芒

这题有毒吧？不用输出二叉树的值，只输出结构吗？【手动哭笑】

发表于 2018-11-15 23:47:35 回复(2)

lingh

c++代码，前序遍历的思想
class TreeToSequence {
public:
    string toSequence(TreeNode* root) {
        // 前序遍历
        if(root==nullptr) return "";
        string res = '(' + forward_order(root) + ')';
        return res;
        
    }
    string forward_order(TreeNode* node)
    {
        if(node==nullptr) return "";
        string res;
        //res.push_back(node->val);
        if(node->left!=nullptr)
        res += '(' + forward_order(node->left) + ')';
        if(node->right!=nullptr)
        res += '(' + forward_order(node->right) + ')';
        return res;
    }
    
};

发表于 2021-03-14 11:53:01 回复(0)

皮蛋秀柚秋

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class TreeToSequence {
public:
    string toSequence(TreeNode* root) {
        if(!root) return "";
        return "("+toSequence(root->left)+toSequence(root->right)+")";
    }
};

发表于 2019-09-21 22:06:14 回复(0)

长昼

谁能给个输入输出的用例，我题都没看懂。。。

发表于 2019-06-14 14:47:06 回复(0)

C/C++

牛客2512095号

string toSequence(TreeNode* root) {
// write code here
string str="";
if(root){
str="("+toSequence(root->left)+toSequence(root->right)+")";
}
return str;
}

发表于 2019-06-14 11:00:46 回复(0)

LSLOFWIND

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/

class TreeToSequence {
public:
string toSequence(TreeNode* root) {
// write code here
if(root==NULL)return "";
else return "("+toSequence(root->left)+toSequence(root->right)+")";
}
};

发表于 2019-03-30 11:55:44 回复(0)

louisfang

import java.util.*;

public class TreeNode {

int val = 0;

TreeNode left = null;

TreeNode right = null;

public TreeNode(int val) {

this.val = val;

}

}*/

public class TreeToSequence {

//每次访问一个节点，都添加括号，按照中序遍历的方法，就可以达到目的。

public String toSequence(TreeNode root) {

StringBuffer sb = new StringBuffer();

inOrder_traval(root, sb);

return sb.toString();

}

public void inOrder_traval(TreeNode root, StringBuffer sb){

if(root == null) return;

sb.append("(");

inOrder_traval(root.left,sb);

inOrder_traval(root.right,sb);

sb.append(")");

}

发表于 2018-08-28 00:55:34 回复(0)

Python

离疏

class TreeToSequence:
    def toSequence(self, root):
        if not root:#该树为空，则返回的字符串也为空
            return ''
        left,right=root.left,root.right
        if left==None and right==None:#左右子树皆为空，则只有该数本身的括号
            return '()'
        else:
            return '('+self.toSequence(left)+self.toSequence(right)+')'

发表于 2018-08-19 15:10:34 回复(0)

C/C++

蛟龙吐火球丰

class TreeToSequence {
public:
    string core(TreeNode* cur)
    {
        string out="";
        if(cur==nullptr)
            return out;       
        if(cur->left)
            out="("+core(cur->left)+")"+out;
        if(cur->right)
            out=out+"("+core(cur->right)+")";
        return out;
    }
    string toSequence(TreeNode* root) {

        return "("+core(root)+")";
    }
};

发表于 2018-05-16 09:06:35 回复(0)

苏觅云

public class TreeToSequence {
    public String toSequence(TreeNode root) {
        // write code here
        if(root==null) return "";
        else return "("+toSequence(root.left)+toSequence(root.right)+")";
    }
}

编辑于 2018-04-26 21:14:51 回复(0)