536. Construct Binary Tree from String
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:
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:
4
/ \
2 6
/ \ /
3 1 5
Note:
- There will only be
'(',')','-'and'0'~'9'in the input string.
算法分析：
在 class Solution 内声明一个 int index=0，用来标记当前应该考察的输入字符串的下标，如果下标所指示的是数字，则读取数字，并增进下标；如果下标所指示的是'(‘，则需要递归调用生成TreeNode的函数，并将结果放在root.left子树中；如果当前字符为’)’,则当前递归调用结束，将 index 增加 1 ，并返回生成的 TreeNode。
在父级的函数调用中，将返回的TreeNode放在root.left，考差当前 index 所指示的字符，如果为'(‘，则继续递归调用函数来生成右子树；如果为’)’,说明当前子树没有右子树，将 index 增加 1，并返回当前TreeNode。
Java 算法实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int index=0;
public TreeNode str2tree(String s) {
int len=s.length();
if(len<1||index>=len){
return null;
}
int val=0;
int ch;
int sign=1;
if(s.charAt(index)=='-'){
sign=-1;
index++;
}
while(index<len&&(ch=s.charAt(index))<='9'&&ch>='0'){
val*=10;
val+=ch-'0';
index++;
}
TreeNode root=new TreeNode(sign*val);
if(index>=len||s.charAt(index)==')'){
index++;
return root;//have no child
}//here now index is pointing to a '(' index++;//now pointing to a number
root.left=str2tree(s);
if(index>=len||s.charAt(index)==')'){
index++;
return root;
}//here it means index is pointing to '('
index++;
root.right=str2tree(s);
if(index>=len||s.charAt(index)==')'){
index++;
}
return root;
}
}
