美文网首页
Lintcode367 Expression Tree Buil

Lintcode367 Expression Tree Buil

作者: 程风破浪会有时 | 来源:发表于2017-11-29 10:18 被阅读0次

    【题目描述】

    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/

    相关文章

      网友评论

          本文标题:Lintcode367 Expression Tree Buil

          本文链接:https://www.haomeiwen.com/subject/pvslvxtx.html