|
4 | 4 | * int val; |
5 | 5 | * TreeNode left; |
6 | 6 | * TreeNode right; |
7 | | - * TreeNode(int x) { val = x; } |
| 7 | + * TreeNode() {} |
| 8 | + * TreeNode(int val) { this.val = val; } |
| 9 | + * TreeNode(int val, TreeNode left, TreeNode right) { |
| 10 | + * this.val = val; |
| 11 | + * this.left = left; |
| 12 | + * this.right = right; |
| 13 | + * } |
8 | 14 | * } |
9 | 15 | */ |
10 | 16 | classSolution { |
11 | | -publicTreeNoderecoverFromPreorder(StringS) { |
12 | | -Map<Integer,TreeNode>map =newHashMap<>(); |
| 17 | +publicTreeNoderecoverFromPreorder(Stringtraversal) { |
| 18 | +Stack<TreeNode>stack =newStack<>(); |
13 | 19 | intidx =0; |
14 | | -intn =S.length(); |
15 | | - |
16 | | -while (idx <n) { |
17 | | -intlevel =0; |
18 | | -StringBuildersb =newStringBuilder(); |
19 | | - |
20 | | -while (idx <n &&S.charAt(idx) =='-') { |
21 | | -level++; |
| 20 | +while (idx <traversal.length()) { |
| 21 | +intdepth =0; |
| 22 | +while (idx <traversal.length() &&traversal.charAt(idx) =='-') { |
| 23 | +depth++; |
22 | 24 | idx++; |
23 | 25 | } |
24 | | - |
25 | | -while (idx <n &&Character.isDigit(S.charAt(idx))) { |
26 | | -sb.append(S.charAt(idx++)); |
| 26 | +intvalue =0; |
| 27 | +while (idx <traversal.length() &&Character.isDigit(traversal.charAt(idx))) { |
| 28 | +value =value *10 +Character.getNumericValue(traversal.charAt(idx++)); |
27 | 29 | } |
28 | | - |
29 | | -TreeNodecurrNode =newTreeNode(Integer.parseInt(sb.toString())); |
30 | | -map.put(level,currNode); |
31 | | -if (level >0) { |
32 | | -TreeNodeparent =map.get(level -1); |
33 | | -if (parent.left ==null) { |
34 | | -parent.left =currNode; |
35 | | - } |
36 | | -else { |
37 | | -parent.right =currNode; |
| 30 | +TreeNodenode =newTreeNode(value); |
| 31 | +while (stack.size() >depth) { |
| 32 | +stack.pop(); |
| 33 | + } |
| 34 | +if (!stack.isEmpty()) { |
| 35 | +if (stack.peek().left ==null) { |
| 36 | +stack.peek().left =node; |
| 37 | + }else { |
| 38 | +stack.peek().right =node; |
38 | 39 | } |
39 | 40 | } |
| 41 | +stack.push(node); |
| 42 | + } |
| 43 | +while (stack.size() >1) { |
| 44 | +stack.pop(); |
40 | 45 | } |
41 | | - |
42 | | -returnmap.get(0); |
| 46 | +returnstack.peek(); |
43 | 47 | } |
44 | 48 | } |