LeetCode 606 Construct String from Binary Tree

题意

给予一颗二叉树，根据前序遍历构建一个字符串, 不过需要在每个元素和他的子元素的外层用 () 包住, 并且需要你不会影响字符串和原始二叉树之间一一对应关系的空括号对.

例 :

给予树：

     1
   /   \
  2     3
 /
4

全部返回应该是: `1(2(4)())(3()())`.
省略掉不必要的括号对后的结果为: `1(2(4))(3)`.


给予树：
     1
   /   \
  2     3
   \  
    4 

返回: "1(2()(4))(3)"

解法

采用深度优先遍历, 需要注意特殊情况: 当一个节点有左子树, 但没有右子树时, 可以省略右子树的 (). 当一个节点有右子树, 但没有左子树, 就不能省略左子树的 ().

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }
        if (t.left == null && t.right == null) {
            return t.val + "";
        } else if (t.left != null && t.right != null) {
            return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")";
        } else if (t.left != null) {
            return t.val + "(" + tree2str(t.left) + ")";
        } else {
            return t.val + "()(" + tree2str(t.right) + ")";
        }
    }
}

Runtime: 6 ms, faster than 84.71% of Java online submissions for Construct String from Binary Tree.
Memory Usage: 37.6 MB, less than 98.36% of Java online submissions for Construct String from Binary Tree.