难度: Medium
Submission
运行时间: 87 ms
内存: 21.4 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 correctBinaryTree(self, root: TreeNode) -> TreeNode:
self.visited_nodes = set()
return self.dfs(root)
def dfs(self, node):
if node is None or node.right in self.visited_nodes:
return None
self.visited_nodes.add(node)
node.right = self.dfs(node.right)
node.left = self.dfs(node.left)
return node
Explain
该题解采用了深度优先搜索（DFS）的方法来解决问题。首先，定义了一个集合 `visited_nodes` 用以记录访问过的节点。在递归函数 `dfs` 中，如果当前节点为空或者当前节点的右子节点已经在 `visited_nodes` 中（即被访问过），则说明存在非法引用，此节点应被删除，返回 `None`。否则，将当前节点添加到 `visited_nodes`，递归处理右子节点和左子节点。通过这种方式，算法从根节点开始，逐层向下检查并剪枝，从而修复二叉树。
时间复杂度: 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 correctBinaryTree(self, root: TreeNode) -> TreeNode:
self.visited_nodes = set() # 存储已访问的节点
return self.dfs(root)
def dfs(self, node):
if node is None or node.right in self.visited_nodes: # 如果节点为空或其右子节点已被访问过
return None # 删除这个节点
self.visited_nodes.add(node) # 添加当前节点到已访问集合
node.right = self.dfs(node.right) # 递归处理右子节点
node.left = self.dfs(node.left) # 递归处理左子节点
return node # 返回修改后的节点
Explore
在算法中使用集合（`set`）而不是列表（`list`）来记录节点，是因为集合提供了更高效的查找性能。集合基于哈希表实现，其平均时间复杂度为O(1)来检查元素是否存在，而列表的查找操作则需要O(n)的时间复杂度，其中n是列表的长度。因此，在需要频繁检查元素是否存在的场景中，使用集合可以显著提高算法的效率。
题解通过检查一个节点的右子节点是否已经存在于`visited_nodes`集合中来判断该节点是否应被删除。这种方法确保只有那些其右子节点已经被访问过、即出现非法引用（循环引用）的节点会被删除。该逻辑保证了只有确实存在问题的节点才会被处理，而所有正常的节点都将保持不变。递归过程中对每个节点的这种检查确保了算法的正确性，防止了错误删除有效节点。
在递归处理节点之前将其添加到`visited_nodes`集合中是必要的，因为这样可以在访问右子节点之前标记当前节点已被访问。这种顺序是为了防止当前节点的右子节点非法地引用到当前节点或其任何祖先节点，这是解题要求的关键部分。在递归进入更深层次的节点之前标记已访问的节点，有助于维护算法的正确性，并且对效率没有负面影响，因为集合的添加操作是O(1)的时间复杂度。
根据题解的逻辑，当一个节点因为其右子节点已经存在于`visited_nodes`中而被删除时，这个节点的左子节点也会被递归地处理。这是因为在`dfs`函数中，如果当前节点需要删除（即返回`None`），那么其左子节点也会通过递归调用`dfs(node.left)`来相应地处理。这确保了所有可能受影响的子节点都会被适当地检查和处理，无论是左子节点还是右子节点。