题目描述

题目：除法求值

给定一个表达式树（以二叉树形式表示），树的每个节点包含一个运算符（+, -, *, /）和可能的一个或两个子节点（叶节点包含整数）。请实现一个函数来计算这个表达式的值。

注意：

1. 除法定义为整数除法，即结果向下取整。
2. 输入保证表达式树是有效的，并且所有运算的结果都在 int 范围内。
3. 输入的二叉树不包含任何多余的节点（即每个节点要么是叶节点，要么有两个子节点）。

示例输入：

    / \
   /   \
  *     +
 / \   / \
3   2 4   5

该树表示的表达式为 (3*2) / (4+5)。

示例输出：

0

因为 (3*2) / (4+5) = 6 / 9 = 0（整数除法）。

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 示例代码

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 示例代码

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() 函数来确保结果向下取整。