LeetCode 1602. 找到二叉樹中最近的右側節點(BFS)

Michael阿明 2021-08-15 22:28:18 阅读数:928

本文一共[544]字,预计阅读时长:1分钟~
leetcode 找到 二叉 中最 最近

文章目錄

1. 題目

給定一棵二叉樹的根節點 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
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

/** * 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阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753127w.html