C++實(shí)現(xiàn)二叉樹的堂兄弟節(jié)點(diǎn)查詢
一.二叉樹的堂兄弟節(jié)點(diǎn)
1.題目描述
在二叉樹中，根節(jié)點(diǎn)位于深度 0 處，每個深度為 k 的節(jié)點(diǎn)的子節(jié)點(diǎn)位于深度 k+1 處。
如果二叉樹的兩個節(jié)點(diǎn)深度相同，但 父節(jié)點(diǎn)不同 ，則它們是一對堂兄弟節(jié)點(diǎn)。
我們給出了具有唯一值的二叉樹的根節(jié)點(diǎn) root ，以及樹中兩個不同節(jié)點(diǎn)的值 x 和 y 。
只有與值 x 和 y 對應(yīng)的節(jié)點(diǎn)是堂兄弟節(jié)點(diǎn)時，才返回 true 。否則，返回 false。
力扣:力扣
2.問題分析
題目中很詳細(xì)的給出了判斷堂兄弟節(jié)點(diǎn)的條件:①兩個節(jié)點(diǎn)深度相同②父節(jié)點(diǎn)不同
由此我們可以通過BFS和DFS找到題目給定的兩個值對應(yīng)的二叉樹結(jié)點(diǎn),記錄這兩個結(jié)點(diǎn)的深度和父節(jié)點(diǎn),最后通過判斷堂兄弟結(jié)點(diǎn)的條件從而判斷是否為堂兄弟結(jié)點(diǎn).
3.代碼實(shí)現(xiàn)
1.BFS解法
// x 的信息
int x;
TreeNode xParent;
int xDepth;
boolean xFound = false;
// y 的信息
int y;
TreeNode yParent;
int yDepth;
boolean yFound = false;
public boolean isCousins(TreeNode root, int x, int y) {
this.x = x;
this.y = y;
LinkedList<TreeNode> queue = new LinkedList<>();
int depth = 0;
if (root != null) {
queue.offer(root);
if (root.val == x || root.val == y) {
return false;
}
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
if (node.left.val == x) {
xParent = node;
xDepth = depth;
}
if (node.left.val == y) {
yParent = node;
yDepth = depth;
}
}
if (node.right != null) {
queue.offer(node.right);
if (node.right.val == x) {
xParent = node;
xDepth = depth;
}
if (node.right.val == y) {
yParent = node;
yDepth = depth;
}
}
}
depth++;
}
return xDepth == yDepth && xParent != yParent;
}2.DFS解法
// x 的信息
int x;
TreeNode xParent;
int xDepth;
boolean xFound = false;
// y 的信息
int y;
TreeNode yParent;
int yDepth;
boolean yFound = false;
public boolean isCousins(TreeNode root, int x, int y) {
this.x = x;
this.y = y;
dfs(root, 0, null);
return xDepth == yDepth && xParent != yParent;
}
public void dfs(TreeNode node, int depth, TreeNode parent) {
if (node == null) {
return;
}
if (node.val == x) {
xParent = parent;
xDepth = depth;
xFound = true;
} else if (node.val == y) {
yParent = parent;
yDepth = depth;
yFound = true;
}
// 如果兩個節(jié)點(diǎn)都找到了，就可以提前退出遍歷
// 即使不提前退出，對最壞情況下的時間復(fù)雜度也不會有影響
if (xFound && yFound) {
return;
}
dfs(node.left, depth + 1, node);
if (xFound && yFound) {
return;
}
dfs(node.right, depth + 1, node);
}二.二叉樹的堂兄弟節(jié)點(diǎn) II
1.題目描述
給你一棵二叉樹的根root，請你將每個節(jié)點(diǎn)的值替換成該節(jié)點(diǎn)的所有 堂兄弟節(jié)點(diǎn)值的和。
如果兩個節(jié)點(diǎn)在樹中有相同的深度且它們的父節(jié)點(diǎn)不同，那么它們互為 堂兄弟。
請你返回修改值之后，樹的根root。
注意，一個節(jié)點(diǎn)的深度指的是從樹根節(jié)點(diǎn)到這個節(jié)點(diǎn)經(jīng)過的邊數(shù)。
力扣:力扣
2.問題分析
每一次只需要求出下一層的所有節(jié)點(diǎn)的和,然后減去非子結(jié)點(diǎn)的值,就是其堂兄弟結(jié)點(diǎn)值的和了.
3.代碼實(shí)現(xiàn)
public TreeNode replaceValueInTree(TreeNode root) {
root.val = 0;
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
ArrayList<TreeNode> tmp = queue;
queue = new ArrayList<>();
int nextLevelSum = 0; // 下一層的節(jié)點(diǎn)值之和
for (TreeNode node : tmp) {
if (node.left != null) {
queue.add(node.left);
nextLevelSum += node.left.val;
}
if (node.right != null) {
queue.add(node.right);
nextLevelSum += node.right.val;
}
}
// 再次遍歷，更新下一層的節(jié)點(diǎn)值
for (TreeNode node : tmp) {
int childrenSum = (node.left != null ? node.left.val : 0) +
(node.right != null ? node.right.val : 0);
if (node.left != null)
node.left.val = nextLevelSum - childrenSum;
if (node.right != null)
node.right.val = nextLevelSum - childrenSum;
}
}
return root;
}
到此這篇關(guān)于C++實(shí)現(xiàn)二叉樹的堂兄弟節(jié)點(diǎn)查詢的文章就介紹到這了,更多相關(guān)C++二叉樹堂兄弟節(jié)點(diǎn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
詳解C++設(shè)計(jì)模式編程中對狀態(tài)模式的運(yùn)用
這篇文章主要介紹了C++設(shè)計(jì)模式編程中對狀態(tài)模式的運(yùn)用,狀態(tài)模式允許一個對象在其內(nèi)部狀態(tài)改變時改變它的行為,對象看起來似乎修改了它的類,需要的朋友可以參考下2016-03-03
C++使用標(biāo)準(zhǔn)庫實(shí)現(xiàn)事件和委托以及信號和槽機(jī)制
這篇文章主要為大家詳細(xì)介紹了C++如何使用標(biāo)準(zhǔn)庫實(shí)現(xiàn)事件和委托以及信號和槽機(jī)制，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，需要的可以參考一下2022-11-11
這篇文章主要介紹了C++實(shí)現(xiàn)大數(shù)乘法算法代碼的相關(guān)資料,需要的朋友可以參考下2015-03-03
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)屏幕截圖功能，截圖自動保存為png格式文件，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
智能指針的本質(zhì)就是使用一個對象來接管一段開辟的空間，在該對象在銷毀的時候，自動調(diào)用析構(gòu)函數(shù)來釋放這段內(nèi)存。本文就來和大家詳細(xì)聊聊智能指針的使用，需要的可以參考一下2022-10-10
本文主要介紹了Qt編寫地圖遷徙圖的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
觀察者模式是極其重要的一個設(shè)計(jì)模式，也是我?guī)啄觊_發(fā)過程中使用最多的設(shè)計(jì)模式，本文首先概述觀察者模式的基本概念和Demo實(shí)現(xiàn)，接著是觀察者模式在C++中的應(yīng)用，最后是對觀察者模式的應(yīng)用場景和優(yōu)缺點(diǎn)進(jìn)行總結(jié)2022-12-12
這篇文章主要為大家介紹了C++Primer之變量，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
本文主要介紹了C++智能指針之shared_ptr的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧<BR>2022-05-05
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)高斯噪聲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06