1，題目描述

?

在二叉樹中，根節點位于深度 0 處，每個深度為 k 的節點的子節點位于深度 k+1 處。

如果二叉樹的兩個節點深度相同，但 父節點不同 ，則它們是一對堂兄弟節點。

我們給出了具有唯一值的二叉樹的根節點 root ，以及樹中兩個不同節點的值 x 和 y 。

只有與值 x 和 y 對應的節點是堂兄弟節點時，才返回 true 。否則，返回 false。

提示：

• 二叉樹的節點數介于?2?到?100?之間。
• 每個節點的值都是唯一的、范圍為?1?到?100?的整數。

?

2，解題思路

二叉樹的題大多數都是用深搜和廣搜來做，思路還是比較清晰的。

要想判斷兩個節點 x 和 y是否為堂兄弟節點，我們就需要求出這兩個節點分別的「深度」以及「父節點」。

因此，我們可以從根節點開始，對樹進行一次遍歷，在遍歷的過程中維護「深度」以及「父節點」這兩個信息。當我們遍歷到 x或 y 節點時，就將信息記錄下來；當這兩個節點都遍歷完成了以后，我們就可以退出遍歷的過程，判斷它們是否為堂兄弟節點了。

?

2-1 方法1 深搜（遞歸）

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def isCousins(self, root: TreeNode, x: int, y: int) -> bool:x_parent=None y_parent=Nonex_depth=Noney_depth=Nonex_found=Falsey_found=Falsedef dfs(node,depth,parent):nonlocal x_parentnonlocal y_parentnonlocal x_depthnonlocal y_depthnonlocal x_foundnonlocal y_foundif(node==None):return Noneif(node.val==x):x_parent=parentx_depth=depth+1x_found=True#找到了x節點if(node.val==y):y_parent=parenty_depth=depth+1y_found=True#找到了y節點if(x_found==True and y_found==True):return#兩個點都找到了dfs(node.left,depth+1,node)if(x_found==True and y_found==True):return#向左下方走遇到了我們要的點，那么結束深搜dfs(node.right, depth + 1, node)#向右下方深搜dfs(root,0,None)if(x_depth==y_depth and x_parent!=y_parent):return Truereturn False

2-2?方法2?廣搜（隊列）

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = rightclass Solution:def isCousins(self, root: TreeNode, x: int, y: int) -> bool:# x 的信息x_parent, x_depth, x_found = None, None, False# y 的信息y_parent, y_depth, y_found = None, None, False# 用來判斷是否遍歷到 x 或 y 的輔助函數def update(node: TreeNode, parent: TreeNode, depth: int):if node.val == x:nonlocal x_parent, x_depth, x_foundx_parent, x_depth, x_found = parent, depth, Trueelif node.val == y:nonlocal y_parent, y_depth, y_foundy_parent, y_depth, y_found = parent, depth, Trueq = [(root, 0)]update(root, None, 0)while q:node, depth = q.pop(0)if node.left:q.append((node.left, depth + 1))update(node.left, node, depth + 1)if node.right:q.append((node.right, depth + 1))update(node.right, node, depth + 1)if x_found and y_found:breakif(x_depth==y_depth and x_parent!=y_parent):return Truereturn False

3 做題心得?

這道題我卡了一段時間，因為一開始parent，depth，found這些變量我設置的是global屬性，結果一直報錯（但是測試樣例可以過）。

后來我想了一下原因，覺得可能是因為leetcode連續測試樣例，那么上一個樣例的結束的時候，兩個found屬性都是true了。那么在下一個樣例開始的時候，這兩個屬性還是true，那么無論如何，檢索完root就結束深搜了。

所以我修改了一下__init__函數（其他的算法部分不變），在__init__函數里面設置兩個found屬性為False，然后就通過了。

以深搜為例：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right x_parent=None y_parent=None x_depth=None y_depth=None x_found=False y_found=False print('1',x_found) class Solution:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightglobal x_foundglobal y_foundx_found=Falsey_found=Falsedef isCousins(self, root: TreeNode, x: int, y: int) -> bool:def dfs(node,depth,parent):global x_parentglobal y_parentglobal x_depthglobal y_depthglobal x_foundglobal y_foundif(node==None):return Noneif(node.val==x):print(node)x_parent=parentx_depth=depth+1x_found=True#找到了x節點elif(node.val==y):print(node)y_parent=parenty_depth=depth+1y_found=Trueif(x_found==True and y_found==True):print(1,x_depth,y_depth,x_parent,y_parent)return Nonedfs(node.left,depth+1,node)if(x_found==True and y_found==True):print(2,x_depth,y_depth,x_parent,y_parent)return None#向左下方走遇到了我們要的點，那么結束深搜dfs(node.right, depth + 1, node)#print(3,x_found)dfs(root,0,None)print(x_depth,y_depth,x_parent,y_parent)if(x_depth==y_depth and x_parent!=y_parent):return Truereturn False

?

總結

以上是生活随笔為你收集整理的文巾解题 leetcode993. 二叉树的堂兄弟节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。