难度: Medium
Submission
运行时间: 124 ms
内存: 44.3 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 findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
q = deque([root])
while q:
m = len(q)
for i in range(m):
root = q.popleft()
if root == u:
return q[0] if i < m - 1 else None
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
Explain
此题解采用层序遍历（广度优先搜索）的方法来寻找最近的右侧节点。首先，将根节点加入队列。每一次循环处理当前层的所有节点，记录当前层的节点数量，然后逐个将这些节点出队。对于每个出队的节点，检查它是否是目标节点u。如果是，并且不是这一层的最后一个节点，那么下一个出队的节点即为最近的右侧节点；如果是这一层的最后一个节点，则返回None。同时，将每个节点的左右子节点依次加入队列以便于下一轮循环处理。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# this.left = left
# this.right = right
class Solution:
def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
q = deque([root]) # 使用双端队列初始化为包含根节点
while q: # 当队列不为空继续循环
m = len(q) # 当前层节点数量
for i in range(m): # 遍历当前层的每个节点
root = q.popleft() # 弹出当前节点
if root == u: # 如果当前节点是目标节点u
return q[0] if i < m - 1 else None # 如果不是最后一个节点则返回下一个节点，否则返回None
if root.left:
q.append(root.left) # 将左子节点加入队列
if root.right:
q.append(root.right) # 将右子节点加入队列
Explore
在使用层序遍历时，队列的特性保证了先进先出的顺序。根节点首先被加入队列，然后在每一层的遍历过程中，每个节点的左右子节点依次被加入队列。由于节点是按照从左到右的顺序被加入的，因此在队列中也将按此顺序被处理和弹出。这样就确保了每一层的节点总是按照从左到右的顺序进行遍历。
如果待查找的节点u不存在于树中，由于在每一层的节点遍历中都是通过节点直接比较来检查是否为u，代码中并没有直接的机制来识别u是否存在于树中。整个遍历过程将会遍历所有节点直到队列为空。由于没有找到u，也就不会触发返回右侧节点的逻辑，最终函数将返回None。
在此题解中，对于每个出队的节点，会首先检查该节点是否为目标节点u。如果是，并且这个节点不是当前层的最后一个节点（即当前层还有其他节点未被处理），则返回队列中的下一个节点作为右侧节点。如果目标节点u是该层的最后一个节点，由于它是最后被处理的节点，执行`q[0]`将会因为队列为空而返回None。因此，如果u是某一层的最后一个节点，代码将自然地返回None，符合题目要求。
如果输入的树是空的（即root为None），由于算法一开始会将root节点加入队列，如果root为None，队列将初始化为空。在while循环的条件是队列非空，因此对于空树的情况，循环体内的代码不会执行，函数将直接结束并返回None。因此，此算法在面对空树时能正常运行，并返回None。