http://bookshadow.com/weblog/2017/03/12/leetcode-construct-binary-tree-from-string/
这道题让我们根据一个字符串来创建一个二叉树，其中结点与其左右子树是用括号隔开，每个括号中又是数字后面的跟括号的模式，这种模型就很有递归的感觉，所以我们当然可以使用递归来做。首先我们要做的是先找出根结点值，我们找第一个左括号的位置，如果找不到，说明当前字符串都是数字，直接转化为整型，然后新建结点返回即可。否则的话从当前位置开始遍历，因为当前位置是一个左括号，我们的目标是找到与之对应的右括号的位置，但是由于中间还会遇到左右括号，所以我们需要用一个变量cnt来记录左括号的个数，如果遇到左括号，cnt自增1，如果遇到右括号，cnt自减1，这样当某个时刻cnt为0的时候，我们就确定了一个完整的子树的位置，那么问题来了，这个子树到底是左子树还是右子树呢，我们需要一个辅助变量start，当最开始找到第一个左括号的位置时，将start赋值为该位置，那么当cnt为0时，如果start还是原来的位置，说明这个是左子树，我们对其调用递归函数，注意此时更新start的位置，这样就能区分左右子树了
https://www.jianshu.com/p/e80659122ba7
https://discuss.leetcode.com/topic/82572/java-recursive-solution
X. Using stack
https://discuss.leetcode.com/topic/82605/java-stack-solution/
https://www.nowtoshare.com/en/Article/Index/20487
http://blog.csdn.net/mcf171/article/details/61616098
You need to construct a binary tree from a string consisting of parenthesis and integers.
The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
You always start to construct the left child node of the parent first if it exists.
Example:
Note:
- There will only be
'(',')','-'and'0'~'9'in the input string.
递归+字符串处理
通过括号匹配将字符串拆解成root, (left), (right)三部分，递归创建二叉树
http://www.cnblogs.com/grandyang/p/6793904.html这道题让我们根据一个字符串来创建一个二叉树，其中结点与其左右子树是用括号隔开，每个括号中又是数字后面的跟括号的模式，这种模型就很有递归的感觉，所以我们当然可以使用递归来做。首先我们要做的是先找出根结点值，我们找第一个左括号的位置，如果找不到，说明当前字符串都是数字，直接转化为整型，然后新建结点返回即可。否则的话从当前位置开始遍历，因为当前位置是一个左括号，我们的目标是找到与之对应的右括号的位置，但是由于中间还会遇到左右括号，所以我们需要用一个变量cnt来记录左括号的个数，如果遇到左括号，cnt自增1，如果遇到右括号，cnt自减1，这样当某个时刻cnt为0的时候，我们就确定了一个完整的子树的位置，那么问题来了，这个子树到底是左子树还是右子树呢，我们需要一个辅助变量start，当最开始找到第一个左括号的位置时，将start赋值为该位置，那么当cnt为0时，如果start还是原来的位置，说明这个是左子树，我们对其调用递归函数，注意此时更新start的位置，这样就能区分左右子树了
https://www.jianshu.com/p/e80659122ba7
https://discuss.leetcode.com/topic/82572/java-recursive-solution
public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) return null;
int firstParen = s.indexOf("(");
int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
TreeNode cur = new TreeNode(val);
if (firstParen == -1) return cur;
int start = firstParen, leftParenCount = 0;
for (int i=start;i<s.length();i++) {
if (s.charAt(i) == '(') leftParenCount++;
else if (s.charAt(i) == ')') leftParenCount--;
if (leftParenCount == 0 && start == firstParen) {cur.left = str2tree(s.substring(start+1,i)); start = i+1;}
else if (leftParenCount == 0) cur.right = str2tree(s.substring(start+1,i));
}
return cur;
} public TreeNode str2tree(String s) {
// Base case
if (s.length() == 0) return null;
// Create root
int i = 0, j = 0;
while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;
TreeNode root = new TreeNode(Integer.parseInt(s.substring(i, j)));
// Left child
if (j < s.length()) {
i = j;
int count = 1;
while (j + 1 < s.length() && count != 0) {
j++;
if (s.charAt(j) == ')') count--;
if (s.charAt(j) == '(') count++;
}
root.left = str2tree(s.substring(i + 1, j));
}
j++;
// Right child
if (j < s.length()) {
root.right = str2tree(s.substring(j + 1, s.length() - 1));
}
return root;
}Input : "4(2(3)(1))(6(5))"
Output : 4 2 3 1 6 5
Explanation :
4
/ \
2 6
/ \ /
3 1 5
We know first character in string is root. Substring inside the first adjacent pair of parenthesis is for left subtree and substring inside second pair of parenthesis is for right subtree as in the below diagram.
We need to find the substring corresponding to left subtree and substring corresponding to right subtree and then recursively call on both of the substrings.
For this first find the index of starting index and end index of each substring.
To find the index of closing parenthesis of left subtree substring, use a stack. Lets the found index is stored in index variable
For this first find the index of starting index and end index of each substring.
To find the index of closing parenthesis of left subtree substring, use a stack. Lets the found index is stored in index variable
X. Using stack
https://discuss.leetcode.com/topic/82605/java-stack-solution/
public TreeNode str2tree(String s) {
Stack<TreeNode> stack = new Stack<>();
for(int i = 0, j = i; i < s.length(); i++, j = i){
char c = s.charAt(i);
if(c == ')') stack.pop();
else if(c >= '0' && c <= '9' || c == '-'){
while(i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
TreeNode currentNode = new TreeNode(Integer.valueOf(s.substring(j, i + 1)));
if(!stack.isEmpty()){
TreeNode parent = stack.peek();
if(parent.left != null) parent.right = currentNode;
else parent.left = currentNode;
}
stack.push(currentNode);
}
}
return stack.isEmpty() ? null : stack.peek();
}https://www.nowtoshare.com/en/Article/Index/20487
http://blog.csdn.net/mcf171/article/details/61616098
