ConstructStringFromBinaryTreeOPT [source code]

public class ConstructStringFromBinaryTreeOPT {
    public String tree2str(TreeNode t) {
        StringBuilder sb = new StringBuilder();
        helper (sb, t);
        return sb.toString();
    }

    public void helper(StringBuilder sb,TreeNode t) {
        if (t != null) {
            sb.append(t.val);
            if (t.left != null || t.right != null) {
                sb.append("(");
                helper(sb,t.left);
                sb.append(")");
                if (t.right != null) {
                    sb.append("(");
                    helper(sb,t.right);
                    sb.append(")");
                }
            }
        }        
    }

    public static void main (String[] args) {
        ConstructStringFromBinaryTreeOPT tester = new ConstructStringFromBinaryTreeOPT();
        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));
    }
}

这个是答案上面的最优解: 13ms;

注意看这里的函数的命名, 叫做 helper. helper 这个概念大概就跟我们常说的 wrapper 这个概念是相对应的.

StringBuilder好像其实跟 String 是一个概念, 不过是一个 mutable 的, 反正大概意思就是类似于是一个pointer to String, 这里就是直接一路传下去(避免了 String 本身一路传下去带来的 cost).
正因为有一个统一的 pointer 来保存所有操作的结果, helper 本身的返回值类型干脆就是 void 了;

这个人的算法首先并不复杂, 但是思路跟最 naive 的算法, 也就是我自己直接写的 ver1的算法的区别还是很大. 我的算法的思路其实就是直接本着从 DFS 本身的修改开始的角度, 考虑怎么放括号, 以及最后怎么删除括号.
但是他这个算法不是这个想法, 这个算法本着conditional addition的思路, 只有当特定的条件满足之后, 才向下搜索, 才搜索下一个 child, etc. 这样的一个思路可以避免很多不必要的recursion call,达到加速的目的; 他这个算法, 其实如果你自己站在一个 traveller 的角度, 按照 DFS 的路线在走, 反而是最自然最容易理解的. 到达一个路口, 我们就考虑如何左下一个决定.
至于括号, 也就是 timestamp 的添加, 在这个思路的框架下, 照样也很简单.

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