1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
private StringBuilder ans;
public String tree2str(TreeNode root) {
if (root == null) {
return "";
}
ans = new StringBuilder();
helper(root);
return ans.toString();
}
private void helper(TreeNode node) {
if (node == null) {
return;
}
ans.append(node.val);
if (node.left == null && node.right == null) {
return;
}
ans.append('(');
helper(node.left);
ans.append(')');
if (node.right != null) {
ans.append('(');
helper(node.right);
ans.append(')');
}
}
}
|
DFS即可. 如果左右都没child, 那直接return, 否则左边即使没有node, 也要把括号加上, 因为如果左边没node, 此时右边一定会有. 这样我们加空括号证明左边没node, 而后面的括号里的东西代表的是右支的东西.
时间复杂度: O(n)
空间复杂度: O(n) 假设每个支都有自己的括号, 那就是n对括号. 再加上n个val, 于是就是3n长度的字符, 也就是O(n). 递归需要用栈, 那就是O(n)
