难度: Medium
Submission
运行时间: 46 ms
内存: 19.5 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
def revalue(root):
if not root: return 0
root.val+= revalue(root.left)+revalue(root.right)
return root.val
revalue(root)
key = root.val/2
#print(root,key)
self.ans = False
def dfs(root):
if not root: return
if root.val == key:
self.ans = True
if root.left:
dfs(root.left)
if root.right:
dfs(root.right)
if root.left: dfs(root.left)
if root.right: dfs(root.right)
return self.ans
Explain
这个题解的思路是先对二叉树进行一次遍历，计算出每个节点的子树和，将其存储在对应节点的val属性中。然后再次遍历二叉树，查找是否存在一个节点，其子树和恰好等于整棵树的节点和的一半。如果找到了这样的节点，就说明可以将树划分为两棵和相等的子树。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
def revalue(root):
if not root: return 0
# 计算当前节点的子树和，并将其存储在节点的val属性中
root.val += revalue(root.left) + revalue(root.right)
return root.val
# 计算每个节点的子树和
revalue(root)
# 目标和为整棵树节点和的一半
key = root.val / 2
self.ans = False
def dfs(root):
if not root: return
# 如果当前节点的子树和等于目标和，说明找到了符合条件的划分
if root.val == key:
self.ans = True
# 递归遍历左子树
if root.left:
dfs(root.left)
# 递归遍历右子树
if root.right:
dfs(root.right)
# 在左右子树中查找符合条件的节点
if root.left: dfs(root.left)
if root.right: dfs(root.right)
return self.ans
Explore
是的，这样的设计会导致原始的节点值信息丢失，这可能会影响到其他需要使用原始节点值的树操作或算法。例如，如果其他算法需要根据原始节点的值进行搜索、排序或构建平衡二叉树等操作，更改val属性将导致这些操作无法正确执行。如果需要保留原始数据，可以考虑使用额外的数据结构（如哈希表）来存储每个节点的子树和，而不直接修改节点的val属性。
根据题解的算法设计，如果根节点的子树和恰好等于整棵树的一半，该情况并未被单独处理，因为算法中没有考虑根节点的子树和是否等于整棵树的一半。实际上，该情况不应被视为有效的划分，因为划分需要将树分成两个独立的非空子树，而根节点的子树和等于整棵树的一半意味着另一半为空，这不符合题目的要求。因此，此情形应当返回false。
如果整棵树的总和是奇数，那么树的总和除以2将得到一个浮点数，这意味着无法找到两个整数子树和相加等于原树总和的情况。因此，在这种情况下，算法应该直接返回false，因为不可能通过整数的子树和来匹配树的总和的一半。在实现时，可以在进行子树和计算之后，检查树的总和是否为奇数，如果是，则直接返回false。
使用全局变量self.ans来记录结果虽然可以简化代码，但这种设计可能导致代码的可读性和可维护性降低，尤其是在多线程环境或者需要多次调用函数的场景中容易引起错误。一种更好的设计是使用递归函数的返回值来传递是否找到符合条件的划分。递归函数可以返回一个布尔值，表示其子树中是否存在符合条件的划分，并在父调用中根据返回值决定是否继续搜索或直接返回结果。这样可以避免使用全局变量，使代码更加模块化和易于理解。