?LeetCode刷題實(shí)戰(zhàn)536： 從字符串生成二叉樹
ou 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.
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例:
輸入: "4(2(3)(1))(6(5))"
輸出: 返回代表下列二叉樹的根節(jié)點(diǎn):
???????4
?????/ \
????2?????6
???/ \ /
??3???1?5???
?
注意:
輸入字符串中只包含 '(', ')', '-'?和 '0'?~ '9'?
空樹由 ""?而非"()"表示。
解題
class?Solution?{
????public?TreeNode str2tree(String s) {
????????if?(s.length() == 0) return?null;
????????StringBuilder value?= new?StringBuilder();
????????TreeNode root = new?TreeNode();
????????int?start = -1; // 第一個(gè)左括號(hào)的位置
????????// 確定根節(jié)點(diǎn)的權(quán)值
????????for?(int?i = 0; i < s.length(); i++) {
????????????if?(s.charAt(i) == '(') {
????????????????root.val = Integer.parseInt(value.toString());
????????????????start = i;
????????????????break;
????????????}
????????????if?(i == s.length() - 1) {
????????????????value.append(s.charAt(i));
????????????????root.val = Integer.parseInt(value.toString());
????????????????return?root;
????????????}
????????????value.append(s.charAt(i));
????????}
????????// 對(duì)左右子樹遞歸求解
????????int?count = 1; // 遇到左括號(hào)則++，遇到右括號(hào)則--
????????for?(int?i = start + 1; i < s.length(); i++) {
????????????if?('('?== s.charAt(i)) count++;
????????????if?(')'?== s.charAt(i)) count--;
????????????if?(count == 0) {
????????????????// 找到了左子樹的區(qū)間
????????????????root.left = str2tree(s.substring(start + 1, i));
????????????????if?(i != s.length() - 1) {
????????????????????// 剩余的就是右子樹的區(qū)間
????????????????????root.right = str2tree(s.substring(i + 2, s.length() - 1));
????????????????}
????????????????break; // 左右子樹整合完畢，結(jié)束
????????????}
????????}
????????return?root;
????}
}