创建递归二叉树？

Question

我有两个堆栈，一个带有操作数，另一个带有运算符。我的问题是将这两个堆栈变成二叉树。

例如，表达式 (2+3)*(4-3)将被翻译成后缀(例如 24+43-* )然后放入两个堆栈3442和 *-+将是堆栈(顶部分别为 3 和 *)。

现在有了这些堆栈，我需要形成一个二叉树

   *
 +    -
2 3  4 3

有没有办法递归地做到这一点？

现在，我有一个这样的算法:

创建树的根，将根的值赋给运算符堆栈中的第一个运算符。将左右指针设置为空。

创建正确的节点，如果存在则为其分配下一个运算符的值，如果不存在则为其分配一个操作数。然后对左节点执行相同操作。

我的问题是使这个递归，或者让它处理许多不同的情况。

谢谢你的帮助。

Answer 1

假设您只有二元运算符

treeNode createNode(operators, operands) {
  // take first operator and create a new treeNode with it. pop it from the operators stack 

  // if it is the last operator in the list then there should be only two operands left in the operands and you can assign them to the left and right child of the treeNode. return this treeNode.

  // if it is not the last operator then split the operands in two stacks equally
  // leftOperands and rightOperands
  // left child becomes createNode(operators, leftoperands)
  // right child becomes createNode(operators, rightoperands)
  // return this treeNode

}