【Lintcode】880. Construct Binary Tree from String

题目地址：

https://www.lintcode.com/problem/construct-binary-tree-from-string/description

给定一个字符串，只含左括号、右括号、负号和$0?9$的数字。要求将其构造为一棵二叉树。构造规则是这样的，字符串要么是空串（则返回空树），要么以一个数开头（可正可负），后面接着两块括号，第一个括号内是左子树对应的字符串，第二个是右子树对应的字符串（当然也可能只有左子树没有右子树）。返回树根。

思路是递归。先解析字符串，解析出树根，树根一定在开头，所以还比较好解析出来。接下来解析左右子树。方式是，用一个变量记录左括号减去右括号数量，当这个变量等于$0$的时候，就意味着解析出来了一个子树，递归构造之，append到树根左边即可。右子树同理。代码如下：

public class Solution {
    /*** @param s: a string* @return: a root of this tree*/public TreeNode str2tree(String s) {
    // write your code hereif (s == null || s.isEmpty()) {
    return null;}// 解析出树根int i = 0;while (i < s.length() && s.charAt(i) != '(') {
    i++;}int r = Integer.parseInt(s.substring(0, i));TreeNode root = new TreeNode(r);// l记录左括号减去右括号数目int l = 0;boolean left = true;for (int j = i; j < s.length(); j++) {
    if (s.charAt(j) == '(') {
    l++;} else if (s.charAt(j) == ')') {
    l--;}if (l == 0 && left) {
    root.left = str2tree(s.substring(i + 1, j));left = false;i = j + 1;} else if (l == 0) {
    root.right = str2tree(s.substring(i + 1, j));}}return root;}
}class TreeNode {
    int val;TreeNode left, right;TreeNode(int x) {
    val = x;}
}

时间复杂度$O(n)$，空间$O(h)$，$h$为树高。