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 "()". 建树用stack，先把root加进stack里，之后遍历字符串，遇到‘(’就进栈，遇到‘)’，弹栈，peek的左节点空就加到左节点，否则加到右节点。注意可能出现“-14”这样的数，用Integer.parseInt(s.substring(i, j))这种方法得到num。代码如下： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode str2tree(String s) { if (s.length() == 0) { return null; } Stack<TreeNode> stack = new Stack<TreeNode>(); char[] chs = s.toCharArray(); int p = 0; while (p < s.length() && chs[p] != '(') { p ++; } TreeNode root = new TreeNode(Integer.parseInt(s.substring(0, p))); stack.push(root); for (int i = p; i < chs.length; i ++) { if (chs[i] == '('){ p = i + 1; while (chs[p] != '(' && chs[p] != ')') { p ++; } stack.push(new TreeNode(Integer.parseInt(s.substring(i + 1, p)))); i = p - 1; } else if (chs[i] == ')') { TreeNode temp = stack.pop(); TreeNode pNode = stack.peek(); if (pNode.left == null) { pNode.left = temp; } else { pNode.right = temp; } } } return root; } }