当前位置： 面试刷题>> 除法求值(经典算法150题)
### 题目描述
题目：**除法求值**
给定一个表达式树（以二叉树形式表示），树的每个节点包含一个运算符（`+`, `-`, `*`, `/`）和可能的一个或两个子节点（叶节点包含整数）。请实现一个函数来计算这个表达式的值。
**注意**：
1. 除法定义为整数除法，即结果向下取整。
2. 输入保证表达式树是有效的，并且所有运算的结果都在 `int` 范围内。
3. 输入的二叉树不包含任何多余的节点（即每个节点要么是叶节点，要么有两个子节点）。
**示例输入**：
```plaintext
/ \
/ \
* +
/ \ / \
3 2 4 5
```
该树表示的表达式为 `(3*2) / (4+5)`。
**示例输出**：
```plaintext
0
```
因为 `(3*2) / (4+5) = 6 / 9 = 0`（整数除法）。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function evalExpression($root) {
if ($root == null) {
return 0;
}
if ($root->left == null && $root->right == null) {
return $root->val;
}
$leftVal = evalExpression($root->left);
$rightVal = evalExpression($root->right);
switch ($root->val) {
case '+':
return $leftVal + $rightVal;
case '-':
return $leftVal - $rightVal;
case '*':
return $leftVal * $rightVal;
case '/':
// 注意：整数除法
return intval($leftVal / $rightVal);
}
}
// 示例用法
$root = new TreeNode('/');
$root->left = new TreeNode('*');
$root->right = new TreeNode('+');
$root->left->left = new TreeNode(3);
$root->left->right = new TreeNode(2);
$root->right->left = new TreeNode(4);
$root->right->right = new TreeNode(5);
echo evalExpression($root); // 输出 0
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def evalExpression(root):
if not root:
return 0
if not root.left and not root.right:
return root.val
left_val = evalExpression(root.left)
right_val = evalExpression(root.right)
if root.val == '+':
return left_val + right_val
elif root.val == '-':
return left_val - right_val
elif root.val == '*':
return left_val * right_val
elif root.val == '/':
# 注意：整数除法
return left_val // right_val
# 示例用法
root = TreeNode('/')
root.left = TreeNode('*')
root.right = TreeNode('+')
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
print(evalExpression(root)) # 输出 0
```
### JavaScript 示例代码
```javascript
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function evalExpression(root) {
if (!root) {
return 0;
}
if (!root.left && !root.right) {
return root.val;
}
const leftVal = evalExpression(root.left);
const rightVal = evalExpression(root.right);
switch (root.val) {
case '+':
return leftVal + rightVal;
case '-':
return leftVal - rightVal;
case '*':
return leftVal * rightVal;
case '/':
// 注意：整数除法
return Math.floor(leftVal / rightVal);
}
}
// 示例用法
const root = new TreeNode('/');
root.left = new TreeNode('*');
root.right = new TreeNode('+');
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(5);
console.log(evalExpression(root)); // 输出 0
```
以上三个示例分别用 PHP、Python 和 JavaScript 实现了题目要求的除法求值功能。注意在整数除法时，PHP 使用了 `intval()` 函数，Python 使用了 `//` 运算符，而 JavaScript 使用了 `Math.floor()` 函数来确保结果向下取整。