# 606. Construct String from Binary Tree

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: string tree2str(TreeNode* t) { return dfs(t); } private: string dfs(TreeNode* root) { if (!root) return ""; const string& rootStr = to_string(root->val); if (root->right) return rootStr + "(" + dfs(root->left) + ")(" + dfs(root->right) + ")"; if (root->left) return rootStr + "(" + dfs(root->left) + ")"; return rootStr + ""; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public String tree2str(TreeNode t) { return dfs(t); } private String dfs(TreeNode root) { if (root == null) return ""; if (root.right != null) return root.val + "(" + dfs(root.left) + ")(" + dfs(root.right) + ")"; if (root.left != null) return root.val + "(" + dfs(root.left) + ")"; return root.val + ""; } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def tree2str(self, t: Optional[TreeNode]) -> str: def dfs(root: Optional[TreeNode]) -> str: if not root: return '' if root.right: return str(root.val) + '(' + dfs(root.left) + ')(' + dfs(root.right) + ')' if root.left: return str(root.val) + '(' + dfs(root.left) + ')' return str(root.val) return dfs(t)