题目大意：
根据二叉树创建字符串
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
1
/ \
2 3
/
4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。 示例 2:
输入: 二叉树: [1,2,3,null,4]
1
/ \
2 3
\
4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。 如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=606
解题思路分析：
二叉树前序遍历即是上左右的顺序。递归时，输出顺序为:
当前节点+ (左子树) + (右子树)
本题关键在于搞清哪些括号是必须的，哪些是可以省略的：
- 如果左子树为空，左子树的括号不能省略。（如果省略，右子树会被误认为是左子树）
- 如果右子树为空，右子树的括号可以省略。
- 如果当前是叶子节点，无需括号。（该层括号在父层时已经被添加过）
实现代码：
public String tree2str(TreeNode t) {
// 根节点为空，返回空字符串
if(t==null) return "";
// 先添加根节点
StringBuilder res = new StringBuilder(String.valueOf(t.val));
// 如果是叶子节点，直接返回
if(t.left==null&&t.right==null) return res.toString();
// 添加左节点，左节点为空时，括号不能省略
if(t.left!=null) res.append("(").append(tree2str(t.left)).append(")");
else res.append("()");
// 添加右节点
if(t.right!=null) res.append("(").append(tree2str(t.right)).append(")");
return res.toString();
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 76.23% of Java online submissions for Construct String from Binary Tree.
Memory Usage: 38.4 MB, less than 94.74% of Java online submissions for Construct String from Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-606-construct-string-from-binary-tree-解题思路分析/