今天刷題祭往,又遇到了二叉樹最近公共祖先問題爹凹,發(fā)現(xiàn)前段時間寫的忘光了衫樊,因此決定寫下來記錄一下了罪。
二叉樹最近公共祖先锭环,leetcode上涉及題目
面試題68-2 二叉樹的最近公共祖先? (同算法題236)
面試題68-1 二叉搜索樹的最近公共祖先? (同算法題235)
算法題1123 最深葉結(jié)點的最近公共祖先
面試題04.08 首個共同祖先(其實同第一項)
面試題68-2 二叉樹的最近公共祖先(算法題236)
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為:“對于有根樹 T 的兩個結(jié)點 p泊藕、q辅辩,最近公共祖先表示為一個結(jié)點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節(jié)點也可以是它自己的祖先)玫锋《贶裕”
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
解題思路:
考慮是二叉樹,基本就是遞歸了
1.如果root是null或者root為p或者q結(jié)點撩鹿,則返回root即可
2.在左子樹和右子樹中分別找p和q的公共祖先谦炬,如果其中一個返回為null,說明p和q都在另一個子樹中节沦,則公共祖先為另一個子樹找到的結(jié)點
3.如果兩個子樹的返回都不是null吧寺,說明p和q分別在兩個子樹中,返回root
c++代碼(并沒有考慮p或者q不存在的情況)
面試題68-1 二叉搜索樹的最近公共祖先? (算法題235)
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先散劫。
百度百科中最近公共祖先的定義為:“對于有根樹 T 的兩個結(jié)點 p稚机、q,最近公共祖先表示為一個結(jié)點 x获搏,滿足 x 是 p赖条、q 的祖先且 x 的深度盡可能大(一個節(jié)點也可以是它自己的祖先)〕N酰”
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof
思路:
本題相對于上一題進(jìn)階點為二叉樹變成了搜索二叉樹纬乍,搜索二叉樹有兩個常用特點:1.查找時可判斷查找val與結(jié)點val大小,若小于當(dāng)前結(jié)點val裸卫,則在左子樹中查找仿贬,若大于,則在右子樹中查找 2.搜索二叉樹的中序遍歷為有序遞增數(shù)組
1.同上題墓贿,如果root為null或root為p或者q茧泪,直接返回root
2.如果p和q都小于當(dāng)前結(jié)點val,則搜索左子樹即可聋袋,若p和q都大于當(dāng)前結(jié)點val队伟,則搜索右子樹即可,若一個大一個小幽勒,則返回當(dāng)前結(jié)點
c++代碼
算法題1123 最深葉結(jié)點的最近公共祖先
給你一個有根節(jié)點的二叉樹嗜侮,找到它最深的葉節(jié)點的最近公共祖先。
回想一下:
葉節(jié)點 是二叉樹中沒有子節(jié)點的節(jié)點
樹的根節(jié)點的?深度?為?0啥容,如果某一節(jié)點的深度為?d锈颗,那它的子節(jié)點的深度就是?d+1
如果我們假定 A 是一組節(jié)點?S?的 最近公共祖先,S?中的每個節(jié)點都在以 A 為根節(jié)點的子樹中咪惠,且 A?的深度達(dá)到此條件下可能的最大值击吱。
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves
思路:
當(dāng)然,可以暴力找到最深的子結(jié)點硝逢,然后兩個找祖先姨拥,之后再依次找到當(dāng)前公共祖先和下一個結(jié)點的最近公共祖先
但是這道題有個比較清奇的思路,考慮當(dāng)前結(jié)點的左子樹深度大于右子樹深度渠鸽,則要在左子樹中尋找叫乌。如果右子樹大于左子樹深度,則在右子樹中尋找徽缚。如果左子樹和右子樹深度相同憨奸,返回當(dāng)前結(jié)點。
1.如果當(dāng)前結(jié)點為空或當(dāng)前結(jié)點為葉子結(jié)點凿试,返回當(dāng)前結(jié)點
2.若當(dāng)前結(jié)點左子樹深度大于右子樹深度排宰,遞歸左子樹,若深度相同那婉,返回當(dāng)前結(jié)點板甘,否則,遞歸右子樹
面試題04.08 首個共同祖先
設(shè)計并實現(xiàn)一個算法详炬,找出二叉樹中某兩個節(jié)點的第一個共同祖先盐类。不得將其他的節(jié)點存儲在另外的數(shù)據(jù)結(jié)構(gòu)中。注意:這不一定是二叉搜索樹呛谜。
思路:同第一道題