难度: Medium
Submission
运行时间: 304 ms
内存: 53.1 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 equalToDescendants(self, root: Optional[TreeNode]) -> int:
ans=0
def dfs(x):
nonlocal ans
if x is None:
return 0
res=dfs(x.left)+dfs(x.right)
if x.val==res:
ans+=1
return res+x.val
dfs(root)
return ans
Explain
这个题解使用了深度优先搜索（DFS）的方法来遍历整个二叉树。对于每个节点，函数 `dfs` 计算并返回该节点所有子节点的值的总和。在返回之前，如果当前节点的值等于其所有子节点的值的总和，则累加计数器 `ans`。最后，整个树遍历完成后，`ans` 包含了所有符合条件的节点的数量。
时间复杂度: O(n)
空间复杂度: O(h)
# 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 equalToDescendants(self, root: Optional[TreeNode]) -> int:
ans=0 # 初始化符合条件的节点计数器
def dfs(x):
nonlocal ans # 允许访问外部作用域中的变量ans
if x is None: # 如果当前节点为空，返回0
return 0
res=dfs(x.left)+dfs(x.right) # 计算左右子树的值之和
if x.val==res: # 如果当前节点的值等于其子节点值之和
ans+=1 # 增加符合条件的节点计数
return res+x.val # 返回当前节点的值与其子节点值之和
dfs(root) # 从根节点开始深度优先搜索
return ans # 返回符合条件的节点总数
Explore
在`dfs`函数中，如果当前节点是叶子节点，其左右子节点均为`None`，因此`dfs(x.left)`和`dfs(x.right)`都会返回0。此时变量`res`的值为0（因为0+0=0）。然后，函数将检查`x.val`是否等于`res`（即0），如果等于则增加计数器`ans`。无论是否增加计数器，叶子节点的返回值总是它自己的值`x.val`。
在比较`x.val`与`res`时，算法确实考虑了节点值可能为负数的情况。算法只简单地比较两者是否相等，不依赖于值的符号。因此，无论节点值是正数、负数还是零，只要节点的值等于其所有子节点的值之和，就会正确地增加计数器。所以，有负数值节点的情况不会影响算法的正确性。
是的，递归的深度可能导致栈溢出，尤其是在处理高度非常大的二叉树时。递归深度基本上等于树的高度。在实际应用中，可以通过以下几种方式来避免栈溢出：1. 使用非递归（迭代）的方法来遍历树，如使用栈来模拟递归过程。2. 尽可能优化递归算法，减少每层递归需要的栈空间。3. 如果使用的编程语言支持，可以尝试增加程序的栈大小限制。4. 考虑使用尾递归优化，尽管在Python中这不是一个内置的优化措施。
对于非平衡二叉树，这种DFS方法的效率可能较低，因为树的高度可能非常大，导致递归深度很大，从而影响性能。尽管如此，由于我们需要访问树中的每个节点以计算其与子节点值之和的关系，任何基于遍历的方法（无论是DFS还是BFS）在最坏情况下的时间复杂度都是O(n)，其中n是树中的节点数。因此，在时间复杂度上，这种DFS方法已经是最优的。为了处理非平衡的情况，可以考虑使用迭代的方法来避免深层递归带来的栈溢出问题，但这并不会提升算法的时间复杂度，只是在实际执行中更为稳定。