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.
-
uis a node in the binary tree rooted atroot.
找到二叉树中最近的右侧节点。
题目很简单，就是常规的BFS，唯一需要注意的是如果在当前层存在u节点的话，需要判断u节点是否是当前层从左往右的最后一个节点，如果不是，他才会有右侧节点。
时间O(n)
空间O(n)
Java实现
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16 class Solution {
17 public TreeNode findNearestRightNode(TreeNode root, TreeNode u) {
18 Queue<TreeNode> queue = new LinkedList<>();
19 queue.offer(root);
20 while (!queue.isEmpty()) {
21 int size = queue.size();
22 for (int i = 0; i < size; i++) {
23 TreeNode cur = queue.poll();
24 if (cur.val == u.val) {
25 if (i < size - 1) {
26 return queue.poll();
27 } else {
28 return null;
29 }
30 }
31 if (cur.left != null) {
32 queue.offer(cur.left);
33 }
34 if (cur.right != null) {
35 queue.offer(cur.right);
36 }
37 }
38 }
39 return null;
40 }
41 }