LeetCode [1602] Find Nearest Right Node in Binary Tree

 1602. Find Nearest Right Node in Binary Tree

Medium

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 of u, or return null if u is 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.

Example 3:

Input: root = [1], u = 1
Output: null

Example 4:

Input: root = [3,4,2,null,null,null,1], u = 4
Output: 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode findNearestRightNode(TreeNode root, TreeNode u) { Queue<TreeNode> que = new LinkedList<>(); que.add(root); while(!que.isEmpty()){ int sz = que.size(); for(int i=0; i<sz; ++i){ TreeNode tn = que.poll(); if(tn.val == u.val){ if(i<sz-1) return que.peek(); } if(tn.left!=null) que.add(tn.left); if(tn.right!=null) que.add(tn.right); } } return null; } }