c********r
发帖数: 286 | 1 突然想起一道题，大概是一个BT or BST， parent node 是加减乘除，children node
是数字，然后要学就运输结果什么的，既不清楚了，哪位大牛知道原题麻烦介绍一下题
目细节，十分感谢！ |
c********r
发帖数: 286 | |
G****A
发帖数: 4160 | 3 prefix-expression
postfix-expression
node
【在 c********r 的大作中提到】
: 突然想起一道题，大概是一个BT or BST， parent node 是加减乘除，children node
: 是数字，然后要学就运输结果什么的，既不清楚了，哪位大牛知道原题麻烦介绍一下题
: 目细节，十分感谢！
|
e****e
发帖数: 418 | 4 +
* -
1 2 3 4
表达式是: (1*2)+(3-4)。
表达式和里面的括号是我为了表述添加的，原题是算出结果就可以了吧。 |
c********t
发帖数: 5706 | 5 post-order traversal是不是就可以?
【在 e****e 的大作中提到】
: +
: * -
: 1 2 3 4
: 表达式是: (1*2)+(3-4)。
: 表达式和里面的括号是我为了表述添加的，原题是算出结果就可以了吧。
|
s****0
发帖数: 117 | |
e****e
发帖数: 418 | 7 我也觉得是post-order traversal。
【在 c********t 的大作中提到】
: post-order traversal是不是就可以?
|
c*******i
发帖数: 30 | 8
node
应该是leaf是数字吧~~其他节点都是运算符~~
用pre-order就行吧~~
【在 c********r 的大作中提到】
: 突然想起一道题，大概是一个BT or BST， parent node 是加减乘除，children node
: 是数字，然后要学就运输结果什么的，既不清楚了，哪位大牛知道原题麻烦介绍一下题
: 目细节，十分感谢！
|
e****e
发帖数: 418 | 9 同意你的分析，我觉得是post-order， 代码如下。
不考虑overflow, a valid such tree has to be a perfect binary tree.
float getResult( TreeNode root ) {
return core( root );
}
float core( TreeNode node ) {
if ( isNum( node.left ) && isNum( node.right ) ) {
return calculate( node, left, right );
}
return calculate( node, core( node.left ), core( node.right ) );
}
isNum()省略。。。
calculate(TeeNode operator, TreeNode operand1, TreeNode operand2 )省略。。。
当运算符是除法的时候，需要检查分母不为零。..
【在 c*******i 的大作中提到】
:
: node
: 应该是leaf是数字吧~~其他节点都是运算符~~
: 用pre-order就行吧~~
|
c********r
发帖数: 286 | |
