[抄题]:
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. - An empty tree is represented by
""
instead of"()"
.
有括号对还是要加q
不用q的做法,就会要多引入变量,有点麻烦:https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100355/Java-Recursive-Solution
用q的做法:https://leetcode.com/problems/construct-binary-tree-from-string/discuss/100359/Java-stack-solution
public class 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);
//节点加完了,就pop出来
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();
}
}