题目

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 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)”

解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

思路

本题的关键是明白输出的规则：

  • 如果左右孩子都空，输出根节点。
  • 如果右孩子为空且左孩子不为空，左孩子要有括号。
  • 剩下两种情况右孩子都不为空，此时不管左孩子是不是空，左孩子都要有括号，当然右孩子也要有。

代码

递归

  1. class Solution {
  2.     public String tree2str(TreeNode root) {
  3.         StringBuilder sb = new StringBuilder();
  4.         if (root == null) {
  5.             return "";
  6.         }
  7.         // 父节点存在
  8.         sb.append(root.val);
  9.         // 左右孩子都空，都没括号
  10.         if (root.left == null && root.right == null) {
  11.             return sb.toString();
  12.         }
  13.         // 到了这里，左孩子一定有括号
  14.         sb.append('(').append(tree2str(root.left)).append(')');
  15.         // 右孩子为空，则没括号
  16.         if (root.right == null) {
  17.             return sb.toString();
  18.         }
  19.         // 右孩子不为空，有括号
  20.         return sb.append('(').append(tree2str(root.right)).append(')').toString();
  21.     }
  22. }