给定一棵二叉树的根节点 root 和树中的一个节点 u ,返回与 u 所在层中距离最近的右侧节点,当 u 是所在层中最右侧的节点,返回 null 。
示例 1:
输入:root = [1,2,3,null,4,5,6], u = 4
输出:5
解释:节点 4 所在层中,最近的右侧节点是节点 5。
示例 2:
输入:root = [3,null,4,2], u = 2
输出:null
解释:2 的右侧没有节点。
示例 3:
输入:root = [1], u = 1
输出:null
示例 4:
输入:root = [3,4,2,null,null,null,1], u = 4
输出:2
提示:
树中节点个数的范围是 [1, 105] 。
1 <= Node.val <= 105
树中所有节点的值是唯一的。
u 是以 root 为根的二叉树的一个节点。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-nearest-right-node-in-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* findNearestRightNode(TreeNode* root, TreeNode* u) {
queue<TreeNode*> q;
q.push(root);
TreeNode* cur;
while(!q.empty())
{
int size = q.size();
while(size--)
{
cur = q.front();
q.pop();
if(size && cur==u)
return q.front();
else if(!size && cur==u)
return NULL;
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
}
return NULL;
}
};
156 ms 84.5 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!