Given the root of a binary tree and a node u in the tree, return the nearest node on the same level that is to the right ofu, or returnnullif uis the rightmost node in its level.
Example 1:
Input: root = [1,2,3,null,4,5,6], u = 4
Output: 5
Explanation: The nearest node on the same level to the right of node 4 is node 5.
Example 2:
Input: root = [3,null,4,2], u = 2
Output: null
Explanation: There are no nodes to the right of 2.
Constraints:
The number of nodes in the tree is in the range [1, 105].
1 <= Node.val <= 105
All values in the tree are distinct.
u is a node in the binary tree rooted at root.
Solutions
Solution 1: BFS
We can use Breadth-First Search, starting from the root node. When we reach node $u$, we return the next node in the queue.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415161718
# 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 = rightclassSolution:deffindNearestRightNode(self,root:TreeNode,u:TreeNode)->Optional[TreeNode]:q=deque([root])whileq:foriinrange(len(q)-1,-1,-1):root=q.popleft()ifroot==u:returnq[0]ifielseNoneifroot.left:q.append(root.left)ifroot.right:q.append(root.right)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcfindNearestRightNode(root*TreeNode,u*TreeNode)*TreeNode{q:=[]*TreeNode{root}forlen(q)>0{fori:=len(q);i>0;i--{root=q[0]q=q[1:]ifroot==u{ifi>1{returnq[0]}returnnil}ifroot.Left!=nil{q=append(q,root.Left)}ifroot.Right!=nil{q=append(q,root.Right)}}}returnnil}
DFS performs a pre-order traversal of the binary tree. The first time we search to node $u$, we mark the current depth $d$. The next time we encounter a node at the same level, it is the target node.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819202122232425
# 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 = rightclassSolution:deffindNearestRightNode(self,root:TreeNode,u:TreeNode)->Optional[TreeNode]:defdfs(root,i):nonlocald,ansifrootisNoneorans:returnifd==i:ans=rootreturnifroot==u:d=ireturndfs(root.left,i+1)dfs(root.right,i+1)d=0ans=Nonedfs(root,1)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcfindNearestRightNode(root*TreeNode,u*TreeNode)*TreeNode{d:=0varans*TreeNodevardfsfunc(*TreeNode,int)dfs=func(root*TreeNode,iint){ifroot==nil||ans!=nil{return}ifd==i{ans=rootreturn}ifroot==u{d=ireturn}dfs(root.Left,i+1)dfs(root.Right,i+1)}dfs(root,1)returnans}