构建表达式树的步骤如下：
- 从左到右扫描后缀表达式中的每个元素。
- 如果遇到操作数，则创建一个只包含该操作数的节点，并将其压入栈中。
- 如果遇到运算符，则创建一个包含该运算符的节点，并从栈中弹出两个操作数节点作为左右子节点，然后将该运算符节点压入栈中。
- 继续处理后缀表达式，直到遍历完所有元素。
- 最终栈中剩下的唯一节点就是根节点，即表达式树的根节点。
比如一个后缀（逆波兰）表达式 53-3*
构建表达式树的代码如下
public static TreeNode constructExpressionTree(String[] tokens) {
LinkedList<TreeNode> stack = new LinkedList<>();
for (String t : tokens) {
switch (t) {
case "+":
case "-":
case "*":
case "/":// 运算符
TreeNode right = stack.pop();
TreeNode left = stack.pop();
TreeNode parent = new TreeNode(t);
parent.left = left;
parent.right = right;
stack.push(parent);
break;
default: // 数字
stack.push(new TreeNode(t));
}
}
return stack.peek();
}
参考
