问题描述 给定一个二叉树，这个二叉树对应一个有效的数值表达式。树的每一个叶子结点都是一个整数，非叶子结点都是加 + 减 - 乘 * 除 \ 这几个运算符之一。算法返回表达式计算的结果。
测试样例
# Input: * / \ + + / \ / \ 3 2 4 5 # Output: 45 # 该表达式为 (3 + 2) * (4 + 5) = 45内容首发于微信公众号IT信息教室，如果您想学习更多AI相关的技能，欢迎搜索关注或微信扫描下方二维码关注～～
参考代码
#!/usr/bin/env python3 # -*- coding: utf-8 -*- class Node: def __init__(self, value): self.value = value self.left = None self.right = None # Type of operations PLUS = '+' MINUS = '-' TIMES = '*' DIVIDE = '/' # Main function # O(N) time, O(log(n)) space # 这是一个简单的递归，对于遍历到的任意个结点 # 如果结点值是运算符，那么递归调用主函数分别判断其左右子树 # 如果结点值是数值，那么就返回该值 def evaluate(root): if root.value == PLUS: return evaluate(root.left) + evaluate(root.right) elif root.value == MINUS: return evaluate(root.left) + evaluate(root.right) elif root.value == TIMES: return evaluate(root.left) * evaluate(root.right) elif root.value == DIVIDE: return evaluate(root.left) / evaluate(root.right) else: return root.value # Test Program tree = Node(TIMES) tree.left = Node(PLUS) tree.right = Node(PLUS) tree.left.left = Node(3) tree.left.right = Node(2) tree.right.left = Node(4) tree.right.right = Node(5) result = evaluate(tree) print(result) # 45 # 二叉树对应的表达式为 (3 + 2) * (4 + 5) = 45