Lintcode367 Expression Tree Build solution 题解
发布在Lintcode题解2018年3月4日view:383
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

The structure of Expression Tree is a binary tree to evaluate certain expressions.

All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

表达树是一个二叉树的结构,用于衡量特定的表达。所有表达树的叶子都有一个数字字符串值。而所有表达树的非叶子都有另一个操作字符串值。

给定一个表达数组,请构造该表达的表达树,并返回该表达树的根。

【题目链接】

www.lintcode.com/en/problem/expression-tree-build/

【题目解析】

观察example,可以看出所有叶节点都为数字。如果给每个元素赋予一个优先级,和 / 为2, + 和 - 为1, 数字为极大值,然后规定优先级越大的越在下,越小的越在上。这样,这道题就转化为构建*Min Tree,和之前的Max Tree做法类似,只是这里维持的是一个递增栈。同时,当遇见“(”时,提高优先级,遇见“)”时,降低优先级。

遍历数组,给每个新来的元素赋予一个val值用以比较优先级。 * 和 / 为2, + 和 - 为1, 数字为极大值。

此时看栈顶元素(若栈为空则直接加入)。为了维持一个递增栈,若栈顶元素比新来元素val大(或相等),则出栈;若栈顶元素比新来元素val小,则break。

若2中栈顶元素出栈,此时若栈为空,则将出栈元素作为新来元素的左节点,并将新来元素加入栈中;若不为空,看新栈顶元素,若新栈顶元素比新来元素val小,则将出栈元素作为新来元素的左孩子,并将新来元素加入栈中;若新栈顶元素比新来元素val大(或相等),则将出栈元素作为新栈顶元素的右节点,重复2-3,直到栈为空或者栈顶元素比新来元素要小,将新来元素加入栈中。

tips:在遍历万整个数组后,多加一个值,将其val赋值为极小,这样所有元素都会出栈并构建成完整的树。

【参考答案】

www.jiuzhang.com/solutions/expression-tree-build/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏