As the normal preorder traversal method, the time complexity is O(n).

```
public String tree2str(TreeNode t) {
if(t==null) return "";
String s = ""+t.val;
String L=tree2str(t.left);
String R=tree2str(t.right);
//if right subtree and left subtree are empty, directly return s
//if only right subtree is empty, we still need to append string L
if(R.equals("")){
if(!L.equals(""))
s+="("+L+")";
}
//if right subtree is not empty, append both strings.
else
s+="("+L+")("+R+")";
return s;
}
```