难度: Medium
Submission
运行时间: 48 ms
内存: 20.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 findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:
def lca(root, p, q):
if root is None or root.val in [p, q]:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left is None:
return right
if right is None:
return left
return root
def dfs(root, v):
if root is None:
return -1
if root.val == v:
return 0
left, right = dfs(root.left, v), dfs(root.right, v)
if left == right == -1:
return -1
return 1 + max(left, right)
g = lca(root, p, q)
return dfs(g, p) + dfs(g, q)
Explain
该题解采用两个主要步骤来找到二叉树中两个节点p和q之间的距离。首先，使用最低公共祖先（LCA）算法找出p和q的共同祖先节点。然后，计算从这个LCA节点到p和q的距离，并将这两个距离相加得到最终的结果。LCA算法通过递归检查当前节点是否为p、q或者它们的共同祖先来工作。找到距离则使用深度优先搜索（DFS），从LCA节点开始向下寻找p和q，计算它们到LCA的距离。
时间复杂度: 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 findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:
def lca(root, p, q):
if root is None or root.val in [p, q]:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left is None:
return right
if right is None:
return left
return root
def dfs(root, v):
if root is None:
return -1
if root.val == v:
return 0
left, right = dfs(root.left, v), dfs(root.right, v)
if left == right == -1:
return -1
return 1 + max(left, right)
g = lca(root, p, q)
return dfs(g, p) + dfs(g, q)
Explore
在LCA函数中，当遇到root为None时，说明已经到达了树的边界，此节点下不再有子节点，因此返回None表示在这个路径上没有找到p或q。当root的值等于p或q时，意味着找到了p或q之一，此时应返回当前节点root，因为它可能是最低公共祖先，或者是路径中一个重要的节点。这种设计是为了在递归过程中标记找到的p或q节点，为后续判断是否已经找到最低公共祖先提供依据。
当LCA函数中左右子树的递归结果均非空时，表示在左子树找到了p（或q），在右子树找到了q（或p）。这意味着当前的root节点正好位于p和q分别位于其左右子树的情况下，因此当前的root节点是p和q的最低公共祖先。选择返回root是因为它是第一个同时拥有向下到p和q的路径的节点，符合最低公共祖先的定义。
在DFS函数中，返回-1代表在当前的子树中没有找到目标节点v。因此，当左右子树的DFS返回值都是-1时，这表示当前节点的左右子树都没有找到目标节点v，因此当前的递归路径不包含目标节点，应继续返回-1向上回溯，表示当前分支下不存在目标节点。
DFS函数使用max函数是为了确保返回的是从当前节点到目标节点v的正确距离。因为在递归过程中，只有一条路径会真正到达目标节点v，而其他路径会返回-1。使用max确保选择了正确的、非-1的路径长度。如果使用min，则当某个子树没有找到目标节点v时，会错误地返回更小的-1，导致无法正确计算从当前节点到目标节点的距离。