LeetCode 1628: Design an Expression Tree With Evaluate Function

Explanation:

To design an Expression Tree with an evaluate function, we can use a binary tree where each node represents an operand or an operator. We can construct the tree recursively by following the order of operations (parentheses, multiplication, division, addition, and subtraction).

For each operator node, we can recursively evaluate its left and right subtrees and then perform the corresponding operation. The evaluate function will return the result of the expression represented by the tree.

Algorithm:

1. Define a TreeNode class to represent each node of the expression tree.
2. Use a stack to parse the input expression and construct the expression tree.
3. Define a recursive evaluate function to calculate the result of the expression.

Time Complexity:

The time complexity for constructing the expression tree and evaluating the expression is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity is also O(n) due to the stack used for constructing the expression tree.

: :

class TreeNode {
    String val;
    TreeNode left;
    TreeNode right;

    public TreeNode(String val) {
        this.val = val;
    }

    public int evaluate() {
        if (val.equals("+")) {
            return left.evaluate() + right.evaluate();
        } else if (val.equals("-")) {
            return left.evaluate() - right.evaluate();
        } else if (val.equals("*")) {
            return left.evaluate() * right.evaluate();
        } else if (val.equals("/")) {
            return left.evaluate() / right.evaluate();
        } else {
            return Integer.parseInt(val);
        }
    }
}