生活随笔
收集整理的這篇文章主要介紹了
LeetCode 742. 二叉树最近的叶节点（建立父节点信息+BFS）
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
1. 題目
給定一個(gè) 每個(gè)結(jié)點(diǎn)的值互不相同 的二叉樹(shù)，和一個(gè)目標(biāo)值 k，找出樹(shù)中與目標(biāo)值 k 最近的葉結(jié)點(diǎn)。
這里，與葉結(jié)點(diǎn) 最近 表示在二叉樹(shù)中到達(dá)該葉節(jié)點(diǎn)需要行進(jìn)的邊數(shù)與到達(dá)其它葉結(jié)點(diǎn)相比最少。
而且，當(dāng)一個(gè)結(jié)點(diǎn)沒(méi)有孩子結(jié)點(diǎn)時(shí)稱(chēng)其為葉結(jié)點(diǎn)。
在下面的例子中，輸入的樹(shù)以逐行的平鋪形式表示。
實(shí)際上的有根樹(shù) root 將以TreeNode對(duì)象的形式給出。
示例
1：
輸入：
root
= [1, 3, 2], k
= 1
二叉樹(shù)圖示：
1/ \
3 2輸出：
2 (或
3)
解釋：
2 和
3 都是距離目標(biāo)
1 最近的葉節(jié)點(diǎn)。示例
2：
輸入：
root
= [1], k
= 1
輸出：
1
解釋： 最近的葉節(jié)點(diǎn)是根結(jié)點(diǎn)自身。示例
3：
輸入：
root
= [1,2,3,4,null
,null
,null
,5,null
,6], k
= 2
二叉樹(shù)圖示：
1/ \
2 3/4/5/6輸出：
3
解釋： 值為
3（而不是值為
6）的葉節(jié)點(diǎn)是距離結(jié)點(diǎn)
2 的最近結(jié)點(diǎn)。注：
root 表示的二叉樹(shù)最少有
1 個(gè)結(jié)點(diǎn)且最多有
1000 個(gè)結(jié)點(diǎn)。
每個(gè)結(jié)點(diǎn)都有一個(gè)唯一的 node
.val ，范圍為
[1, 1000]。
給定的二叉樹(shù)中有某個(gè)結(jié)點(diǎn)使得 node
.val
== k。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/closest-leaf-in-a-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
2. 解題
- dfs 建立父節(jié)點(diǎn)信息，找到 k 節(jié)點(diǎn)，加入隊(duì)列
- BFS，向子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行BFS搜索，第一個(gè)找到的葉子節(jié)點(diǎn)為答案
class Solution {unordered_map
<TreeNode
*,TreeNode
*> father
;queue
<TreeNode
*> q
;unordered_set
<TreeNode
*> visited
;
public:int findClosestLeaf(TreeNode
* root
, int k
) {father
[root
] = NULL;dfs(root
, k
);int size
;TreeNode
* cur
;while(!q
.empty()){size
= q
.size();while(size
--){cur
= q
.front();q
.pop();if(!cur
->left
&& !cur
->right
)return cur
->val
;if(cur
->left
&& !visited
.count(cur
->left
)){q
.push(cur
->left
);visited
.insert(cur
->left
);}if(cur
->right
&& !visited
.count(cur
->right
)){q
.push(cur
->right
);visited
.insert(cur
->right
);}if(father
[cur
] && !visited
.count(father
[cur
])){q
.push(father
[cur
]);visited
.insert(father
[cur
]);}}}return -1;}void dfs(TreeNode
* root
, int k
) {if(!root
) return;if(root
->val
== k
){q
.push(root
);visited
.insert(root
);}if(root
->left
)father
[root
->left
] = root
;if(root
->right
)father
[root
->right
] = root
;dfs(root
->left
,k
);dfs(root
->right
,k
);}
};
28 ms 22.9 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！
總結(jié)
以上是生活随笔為你收集整理的LeetCode 742. 二叉树最近的叶节点（建立父节点信息+BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
