需要帮助从二叉树构造带括号的字符串

Question

我正在尝试解决以下算法问题：

你需要用前序遍历的方式从二叉树中构造一个括号和整数组成的字符串

空节点需要用空括号“()”表示。并且你需要省略所有不影响字符串和原始二叉树之间一对一映射关系的空括号对。

示例 1：输入：二叉树：[1,2,3,4]

输出：“1(2(4))(3)”

解释：原来应该是“1(2(4)())(3()())”, 但是你需要省略所有不必要的空括号对。它将是“1(2(4))(3)”。

示例 2：输入：二叉树：[1,2,3,null,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)"

只有两个工作，但是，我对第三个有问题，无法发现我哪里出错了。

Answer 1

堆栈使事情变得有点复杂。错误在于最终您会在最后一个测试用例中弹出堆栈两次，这会弄乱开闭括号。我删除了堆栈并使代码更容易调试。然而，我使用了双栈方法来解释算术表达式，但在这里似乎没有必要。

您可以在这个沙箱中试用代码：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("");
};

这个版本似乎能产生您想要的结果。不过那很有趣！

Answer 2

正如用户@Jonas Wilms 提到的，我认为没有必要使用堆栈来解决这个问题。我个人觉得使用递归方法更常见（我认为它更有效/可读）。

这是代码

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 = (tree) => {

    const dfs = (current) => {
        if (current === null) return ''

        let result = current.val.toString(); // in fact you don't need toString() here, but has a better readability

        const left = current.left;
        const right = current.right;

        if (left || right) {
            result += '(' + dfs(left) + ')';
        } 
        if (right) {
            result += '(' + dfs(right) + ')';
        }
        return result
    }
    return dfs(tree);
}

const tree1 = 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(tree1)) // "1(2(4))(3)"
console.log(tree2str(tree2)) // "1(2()(4))(3)"
console.log(tree2str(tree3)) // "1(2(3)(4))"

我试图使代码尽可能简单，而且我很确定有办法改进它。如果任何其他输入测试不起作用，请发表评论。这是一个很好的挑战。干杯:)

需要帮助从二叉树构造带括号的字符串

Need help constructing string with parenthesis from Binary Tree

javascript

arrays

stack

binary-tree

depth-first-search