1602. Find Nearest Right Node in Binary Tree

https://leetcode.com/problems/find-nearest-right-node-in-binary-tree/

Brutal force

from collections import deque
class Solution:
    def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> TreeNode:
        level = deque()
        level.append(root)
        while level:
            n = len(level)
            #print(level)
            for i in range(n):
                curr = level.popleft()
                if curr != None and curr.val == u.val:
                    while i < n-1 and level[0] == None:
                        i+=1
                        level.popleft()
                    if i == n-1:
                        return None
                    return level.popleft()
                if curr:
                    level.append(curr.left)
                    level.append(curr.right)
                
        return None
        

优化 right left bfs 顺序调一下，这样可以用last记录

from collections import deque
class Solution:
    def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> TreeNode:
        level = deque()
        level.append(root)
        
        while level:
            n = len(level)
            #print(level)
            last = None
            for i in range(n):
                curr = level.popleft()
                if curr == u:
                    return last
                if curr.right:
                    level.append(curr.right)
                if curr.left:
                    level.append(curr.left)
                last = curr
                
        return None