检查两棵二叉表达式树是否等价

Submission

运行时间: 270 ms

内存: 17.9 MB

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=" ", left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
        has = [0] * 26
        def dfs(node):
            
            if node.val != "+":
                has[ord(node.val)-97] += 1
            else:
                dfs(node.left)
                dfs(node.right)
        dfs(root1)
        has = [-i for i in has]
        dfs(root2)
        return all(i==0 for i in has)

Explain

这个题解采用了深度优先搜索（DFS）来遍历两棵二叉表达式树，同时使用一个数组来统计每个字母节点的出现次数。在第一次DFS遍历时，遍历root1树，对每个字母节点增加其出现次数。在第二次DFS遍历时，遍历root2树，对每个字母节点减少其在数组中的计数。最后，检查数组中的所有值是否都为0，以确定两棵树是否等价。此方法假设表达式树只包含小写字母和'+'节点。

时间复杂度: O(n)

空间复杂度: O(h)

class Node(object):
    def __init__(self, val=' ', left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
        has = [0] * 26  # 创建数组来计数26个字母
        def dfs(node):
            if node.val != '+':  # 如果节点不是'+'，则是字母节点
                has[ord(node.val)-97] += 1  # 增加对应字母的计数
            else:
                dfs(node.left)  # 递归访问左子树
                dfs(node.right)  # 递归访问右子树
        dfs(root1)  # 遍历第一棵树，增加计数
        has = [-i for i in has]  # 将计数数组中的每个数值取反
        dfs(root2)  # 遍历第二棵树，实际上是减少计数
        return all(i == 0 for i in has)  # 检查所有计数是否为0，以确认两树等价

Explore

在处理第二棵树时选择将数组中的计数值取反，是为了通过减法操作来抵消第一棵树中相应字母的计数。这样做的好处是，如果两棵树结构等价，那么所有字母的最终计数应该都会归零，即所有在第一棵树中增加的计数都会被第二棵树中相同的字母减去。如果仍然使用加法，我们则需要在最后对每个字母计数进行检查，确保它们是否都为零，这实际上增加了操作的复杂性。使用取反后的减法可以直接在遍历第二棵树时完成这一验证步骤，使逻辑更为直接和清晰。

这个解法主要是针对只包含字母和'+'节点的表达式树设计的。如果树中存在其他类型的操作符或节点（比如'-'、'*'等），当前的DFS方法将无法正确处理，因为它只识别字母和'+'。对于包含其他操作符的情况，需要对DFS方法进行适当的修改或扩展，以确保能够正确解析和计算这些不同类型的节点。

是的，这种方法仍然可以判断两棵树是否等价，即使它们的左右子树被互换。因为此方法基于对字母的计数而不是树的具体结构。只要两棵树包含相同数量的每个字母，无论这些字母的具体位置如何，最终的字母计数都应该归零，表明两棵树是等价的。这种方法有效地抽象了树的结构，只关注了节点的内容。

确保递归过程中不出现栈溢出错误通常依赖于树的最大深度和系统的栈大小。在实际应用中，可以通过几种方法来减少栈溢出的风险：1. 使用尾递归优化，虽然Python默认不支持尾递归优化，但可以通过代码重构模拟。2. 如果可能，转换为使用迭代的方法，如使用栈来模拟递归过程。3. 增加系统的栈大小（如果环境允许）。4. 在设计上尽量保持树的平衡，避免创建极端不平衡的树结构。对于特别深的树，更推荐使用迭代方法处理，以避免递归深度过大引起的问题。