ConstructStringFromBinaryTree [source code]

public class ConstructStringFromBinaryTree {
    public String tree2str(TreeNode t) {
        if (t == null) return "";
        String res = "" + t.val;        // quick trick to cast int to string
        String left = tree2str(t.left);
        String right = tree2str(t.right);
        if (left.equals("")) {
            if (right.equals("")) res = res;
            else res += "()" + "(" + right + ")";
        } else {
            if (right.equals("")) res += "(" + left + ")";
            else res += "(" + left + ")" + "(" + right + ")";
        }
        return res;
    }

    public static void main (String[] args) {
        ConstructStringFromBinaryTree tester = new ConstructStringFromBinaryTree();
        TreeNode input1 = 
        new TreeNode(1, 
            new TreeNode(2, 
                new TreeNode(4),
                null
                ),
            new TreeNode(3)
            );
        assert tester.tree2str(input1) == "1(2(4))(3)" : "fail 1";
        System.out.println(tester.tree2str(input1));
    }
}

这个是一个比较常规的题目, 就是一个tree traversal, 至于括号, 也没有什么神奇的地方, 就是 DFS 里面的timestamp 而已.
这个问题稍微难一点的地方就是空括号的删除操作. 观察给出的两个例子, 只有当left chile empty but right child not empty的时候括号不能删除(要会合理的总结规律). 不过这个先不急. 先把一个最常规的 traversal 写出来, 然后再考虑怎么处理空括号;

这里最后的输出的结果是一个 string, 这个 string 当然可以用 accum 的形式, 在recursion 的过程一直传下去, 不过既然知道是 java,其实也可以直接作为instance var;

虽然这个题目整体不难, 不过做的时候还是花了不少时间, 主要是对 tree 还是不太熟悉.

这里有一个思维转变的过程, 就是如果按照传统的dfs timestamp的思路, 肯定是更习惯在每个 children 的层面来控制括号的添加, 但是看看给出的例子, 可以看到最外层是没有括号的, 也就是说这个问题里面括号, 或者 timestamp 的添加, 应该由 parent 来控制.
这两者之间的差别到底怎么体现, 刚开始接触的话可能有点不熟练. 毕竟无论是 parent 还是 child, 其实共用的是相同的 code. 其实最后的差别体现的地方就是你每一个 level 的返回值怎样组织. 其他地方差别都不大, 思路稍微对应转换一下就行了.

比如如果是由 child 决定, 那么整个 output 外层肯定是有括号的. 同时在nested if else的部分, if 里面判断的对象就应该是"()" 而不是"".

注意这里有一个小技巧, 就是在这里的 nested if else里面我没有直接就 return, 而是先把 res 怎么样, 然后最后统一return res;
其实是可以直接 return 的, 不过这样统一 exit 的一个好处在于调试的时候方便一些: 如果需要在 return 之前 print 结果, 只要修改一个地方就行了.

算法速度是34ms, 64%, 应该还是有改进空间;

Problem Description

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".
Example 2:
Input: Binary tree: [1,2,3,null,4]
1
/ \
2 3
\
4

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Subscribe to see which companies asked this question.

Hide Tags Tree String
Hide Similar Problems (M) Construct Binary Tree from String