Leetcode 993. 二叉樹的堂兄弟節(jié)點

題目描述

在二叉樹中送朱,根節(jié)點位于深度 0 處娘荡,每個深度為 k 的節(jié)點的子節(jié)點位于深度 k+1 處。

如果二叉樹的兩個節(jié)點深度相同驶沼,但父節(jié)點不同炮沐,則它們是一對堂兄弟節(jié)點。

我們給出了具有唯一值的二叉樹的根節(jié)點 root回怜,以及樹中兩個不同節(jié)點的值 x 和 y大年。

只有與值 x 和 y 對應的節(jié)點是堂兄弟節(jié)點時,才返回 true玉雾。否則翔试,返回 false。

層次遍歷

這里要判斷的是兩個節(jié)點在同一個深度复旬,且父節(jié)點不相同垦缅。可以進行層次遍歷驹碍,判斷兩個節(jié)點是否在同一層壁涎,且父節(jié)點不相同。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes=[root]
        while nodes:
            flag,vals=False,[]
            for i in range(len(nodes)):
                node=nodes.pop(0)
                if node.left and node.right:
                    if (node.left.val==x and node.right.val==y) or (node.left.val==y and node.right.val==x):
                        return False
                if node.left:
                    nodes.append(node.left)
                    vals.append(node.left.val)
                    if node.left.val in [x,y]:
                        flag=True
                if node.right:
                    nodes.append(node.right)
                    vals.append(node.right.val)
                    if node.right.val in [x,y]:
                        flag=True
            if flag:
                return x in vals and y in vals
        return False

遞歸遍歷

因為節(jié)點屬性中沒有父節(jié)點指針志秃,這里不妨定義 par 指向節(jié)點的父節(jié)點粹庞。以 depth 存儲節(jié)點對應的深度,則父節(jié)點不為空時洽损,節(jié)點的深度為父節(jié)點深度加一,父節(jié)點為空革半,則節(jié)點深度為零碑定。因為題目要求還需要判斷兩個節(jié)點的父節(jié)點是否相同,以 parent 存儲節(jié)點對應的父節(jié)點又官。前序遍歷二叉樹延刘,可獲得所有節(jié)點對應的深度及父節(jié)點。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        depth,parent={},{}
        def cou(root,par):
            if root:                
                depth[root.val]=depth[par.val]+1 if par else 0
                parent[root.val]=par
                cou(root.left,root)
                cou(root.right,root)
        cou(root,None)
        return depth[x]==depth[y] and parent[x]!=parent[y]
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末六敬,一起剝皮案震驚了整個濱河市碘赖,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖普泡,帶你破解...
    沈念sama閱讀 212,080評論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件播掷,死亡現(xiàn)場離奇詭異,居然都是意外死亡撼班,警方通過查閱死者的電腦和手機歧匈,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,422評論 3 385
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來砰嘁,“玉大人件炉,你說我怎么就攤上這事“妫” “怎么了斟冕?”我有些...
    開封第一講書人閱讀 157,630評論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長缅阳。 經常有香客問我磕蛇,道長,這世上最難降的妖魔是什么券时? 我笑而不...
    開封第一講書人閱讀 56,554評論 1 284
  • 正文 為了忘掉前任孤里,我火速辦了婚禮,結果婚禮上橘洞,老公的妹妹穿的比我還像新娘捌袜。我一直安慰自己,他們只是感情好炸枣,可當我...
    茶點故事閱讀 65,662評論 6 386
  • 文/花漫 我一把揭開白布虏等。 她就那樣靜靜地躺著,像睡著了一般适肠。 火紅的嫁衣襯著肌膚如雪霍衫。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,856評論 1 290
  • 那天侯养,我揣著相機與錄音敦跌,去河邊找鬼。 笑死逛揩,一個胖子當著我的面吹牛柠傍,可吹牛的內容都是我干的。 我是一名探鬼主播辩稽,決...
    沈念sama閱讀 39,014評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼惧笛,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了逞泄?” 一聲冷哼從身側響起患整,我...
    開封第一講書人閱讀 37,752評論 0 268
  • 序言:老撾萬榮一對情侶失蹤拜效,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后各谚,有當地人在樹林里發(fā)現(xiàn)了一具尸體紧憾,經...
    沈念sama閱讀 44,212評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,541評論 2 327
  • 正文 我和宋清朗相戀三年嘲碧,在試婚紗的時候發(fā)現(xiàn)自己被綠了稻励。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,687評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡愈涩,死狀恐怖望抽,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情履婉,我是刑警寧澤煤篙,帶...
    沈念sama閱讀 34,347評論 4 331
  • 正文 年R本政府宣布,位于F島的核電站毁腿,受9級特大地震影響辑奈,放射性物質發(fā)生泄漏。R本人自食惡果不足惜已烤,卻給世界環(huán)境...
    茶點故事閱讀 39,973評論 3 315
  • 文/蒙蒙 一鸠窗、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧胯究,春花似錦稍计、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,777評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至剥哑,卻和暖如春硅则,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背株婴。 一陣腳步聲響...
    開封第一講書人閱讀 32,006評論 1 266
  • 我被黑心中介騙來泰國打工怎虫, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人困介。 一個月前我還...
    沈念sama閱讀 46,406評論 2 360
  • 正文 我出身青樓揪垄,卻偏偏與公主長得像,于是被迫代替她去往敵國和親逻翁。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,576評論 2 349

推薦閱讀更多精彩內容