我正在尝试解决以下算法问题：
您需要使用预遍历方法从二叉树构造一个由括号和整数组成的字符串。
空节点需要用空括号对“（）”表示。并且您需要忽略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例1：输入：二叉树：[1,2,3,4]
1
/ \
2 3
/
4
输出：“ 1（2（4））（3）”
说明：Originallay它必须为“ 1（2（4）（））（3（）（））”，但是您需要省略所有不必要的空括号对。它将是“ 1（2（4））（3）”。
示例2：输入：二叉树：[1,2,3，null，4]
1
/ \
2 3
\
4
输出：“ 1（2（）（4））（3）”
说明：与第一个示例几乎相同，除了我们不能省略第一个括号对来破坏输入和输出之间的一对一映射关系。
我写了以下代码：
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
}
}
const tree2str = (t) => {
const result = []
const stack = []
const dfs = (current) => {
if (current === null) return
result.push(current.val)
if (!current.left && current.right) result.push('(')
if (current.left) {
result.push('(')
stack.push(')')
dfs(current.left)
}
while (stack.length) {
result.push(stack.pop())
}
if (!current.left && current.right) stack.push(')')
if (current.right) {
result.push('(')
stack.push(')')
dfs(current.right)
}
}
dfs(t)
return result.join('')
}
我到目前为止的测试用例：
const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3))
const tree2 = new TreeNode(1, new TreeNode(2, null, new TreeNode(4)), new TreeNode(3))
const tree3 = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)))
console.log(tree2str(tree)) // "1(2(4)())(3()())" ==> "1(2(4))(3)"
console.log(tree2str(tree2)) // "1(2()(4))(3)"
console.log(tree2str(tree3)) // "1(2(3)(4))" instead got "1(2(3))(4)"
但是只有两项工作，我在第三项上遇到了麻烦，无法发现我要去哪里。
堆栈使事情变得更加复杂。错误是最终您将在最后一个测试用例中弹出堆栈两次，这会弄乱开闭括号。我删除了堆栈，并使代码更易于调试。但是，我已经使用双栈方法来解释算术表达式，但是这里似乎没有必要。
您可以在以下沙箱中尝试代码：https : //codesandbox.io/s/need-help-constructing-string-with-parenthesis-from-binary-tree-p3sk3? file =/ src/ index.js
const tree2str = t => {
const result = [];
const dfs = current => {
if (!current) {
return;
}
const { val, left, right } = current;
if (val !== null && val !== undefined) {
result.push(val);
if (left) {
result.push("(");
dfs(left);
result.push(")");
} else if (!left && right) {
result.push("()");
}
if (right) {
result.push("(");
dfs(right);
result.push(")");
}
}
};
dfs(t);
return result.join("");
};
这个版本似乎产生您想要的结果。不过那很有趣！
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句