根据二叉树创建字符串
难度:
标签:
题目描述
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4] 输出："1(2()(4))(3)" 解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
提示：
- 树中节点的数目范围是
[1, 104] -1000 <= Node.val <= 1000
代码结果
运行时间: 30 ms, 内存: 17.3 MB
/*
思路：
1. 使用递归方法遍历二叉树，并使用StringBuilder构造字符串。
2. 为了利用Java Stream API，可以使用辅助方法将子树转换为字符串，并在主方法中进行合并。
3. 处理空节点和只有右子节点的情况。
*/
import java.util.Optional;
import java.util.stream.Stream;
public class Solution {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public String tree2str(TreeNode t) {
if (t == null) return "";
return helper(t).orElse("");
}
private Optional<String> helper(TreeNode t) {
if (t == null) return Optional.empty();
String left = helper(t.left).map(s -> "(" + s + ")").orElse(t.right != null ? "()" : "");
String right = helper(t.right).map(s -> "(" + s + ")").orElse("");
return Optional.of(t.val + left + right);
}
}
解释
方法:
这个题解采用递归的方式，通过前序遍历二叉树来构造字符串。对于每个节点，先将节点的值转化为字符串，然后递归处理左子树和右子树。如果左子树为空而右子树不为空，需要保留左子树的空括号对。最后将左右子树的结果用括号括起来，与当前节点的值拼接。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归函数中，如果当前节点为空，返回的是空字符串而非一对空括号。这种设计对最终字符串格式有什么影响？
▷🦆
为什么在处理右子树非空但左子树为空的情况时，必须包含一个空的括号对来代表左子树？
▷🦆
在递归处理中，对于叶子节点直接返回节点值，这种处理是否会影响对更复杂树结构的正确描述？
▷相关问题
寻找重复的子树
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1] 输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null] 输出：[[2,3],[3]]
提示：
- 树中的结点数在
[1, 5000]范围内。 -200 <= Node.val <= 200