yijiema1991
BAN USERMy solution is to use recursive method, under one level when the left child or the right child of the root is a (...) parenthesis expression, then this method is called again recursively. Then, at the same level after the left child(noticed: this case does not happen to right child),
I go through the parenthesis expression represented by the left child. When will I stop? Well, I use a stack to store every '(' left parenthesis I encountered, and if I met a ')' parenthesis, I pop an element and until stack is empty. Where is the place where the right child of the current level been placed.
The code is like:
public static TreeNode generate(int start, String str) {
if (str == null || start > str.length() - 1) return null;
int pointer = start;
TreeNode root = new TreeNode(str.charAt(pointer));
pointer += 2;
if (str.charAt(pointer) == '(') {
root.left = generate(pointer + 1, str);
Stack<Character> stack = new Stack<Character>();
stack.push('(');
while (!stack.isEmpty()) {
char temp = str.charAt(++pointer);
if (temp == '(') {
stack.push(temp);
} else if (temp == ')') {
stack.pop();
} else {
// do nothing
}
}
// now pointer points to ')'
} else {
root.left = new TreeNode(str.charAt(pointer));
}
pointer += 2;
if (str.charAt(pointer) == '(') {
root.right = generate(pointer + 1, str);
Stack<Character> stack = new Stack<Character>();
stack.push('(');
while (!stack.isEmpty()) {
char temp = str.charAt(++pointer);
if (temp == '(') {
stack.push(temp);
} else if (temp == ')') {
stack.pop();
} else {
// do nothing
}
}
// now pointer points to ')'
} else {
root.right = new TreeNode(str.charAt(pointer));
}
return root;
}
The runtime is tricky, at the first glance, it is easy to say it is O(n^2). But thinking more, I would say it is closed to O(nlogn). Anyone have a better idea?
- yijiema1991 January 13, 2015
This takes O(n^2) which is not good...
- yijiema1991 January 22, 2015