網際網路公司高頻面試題目:一網打盡二叉樹!(三十三道題目精講)

2020-10-26 代碼隨想錄

二叉樹大總結!

不知不覺二叉樹已經和我們度過了「三十三天」,代碼隨想錄裡已經發了「三十三篇二叉樹的文章」,詳細講解了「30+二叉樹經典題目」,一直堅持下來的錄友們一定會二叉樹有深刻理解了。

在每一道二叉樹的題目中,我都使用了「遞歸三部曲」來分析題目,相信大家以後看到二叉樹,看到遞歸,都會想:返回值、參數是什麼?終止條件是什麼?單層邏輯是什麼?

而且「幾乎每一道題目我都給出對應的迭代法」,可以用來進一步提高自己。

下面Carl把分析過的題目分門別類,可以幫助新錄友循序漸進學習二叉樹也方便老錄友面試前快速複習,看到一個標題,就回想一下對應的解題思路,這樣很快就可以系統性的複習一遍二叉樹了。

公眾號的發文順序,就是循序漸進的,所以如下分類基本就是按照文章發文順序來的,我再做一個系統性的分類。

二叉樹的理論基礎

  • :二叉樹的種類、存儲方式、遍歷方式、定義方式

二叉樹的遍歷方式

  • 深度優先遍歷
    • :遞歸三部曲初次亮相
    • :通過棧模擬遞歸
  • 廣度優先遍歷
    • :通過隊列模擬

求二叉樹的屬性

    • 遞歸:後序,比較的是根節點的子樹與右子樹是不是相互翻轉
    • 迭代:使用隊列/棧將兩個節點順序放入容器中進行比較
    • 遞歸:後序,求根節點最大高度就是最大深度,通過遞歸函數的返回值做計算樹的高度
    • 迭代:層序遍歷
    • 遞歸:後序,求根節點最小高度就是最小深度,注意最小深度的定義
    • 迭代:層序遍歷
    • 遞歸:後序,通過遞歸函數的返回值計算節點數量
    • 迭代:層序遍歷
    • 遞歸:後序,注意後序求高度和前序求深度,遞歸過程判斷高度差
    • 迭代:效率很低,不推薦
    • 遞歸:前序,方便讓父節點指向子節點,涉及回溯處理根節點到葉子的所有路徑
    • 迭代:一個棧模擬遞歸,一個棧來存放對應的遍歷路徑
    • 詳解二叉樹:找所有路徑中遞歸如何隱藏著回溯
    • 遞歸:後序,必須三層約束條件,才能判斷是否是左葉子。
    • 迭代:直接模擬後序遍歷
    • 遞歸:順序無所謂,優先左孩子搜索,同時找深度最大的葉子節點。
    • 迭代:層序遍歷找最後一行最左邊
    • 遞歸:順序無所謂,遞歸函數返回值為bool類型是為了搜索一條邊,沒有返回值是搜索整棵樹。
    • 迭代:棧裡元素不僅要記錄節點指針,還要記錄從頭結點到該節點的路徑數值總和

二叉樹的修改與構造

    • 遞歸:前序,交換左右孩子
    • 迭代:直接模擬前序遍歷
    • 遞歸:前序,重點在於找分割點,分左右區間構造
    • 迭代:比較複雜,意義不大
    • 遞歸:前序,分割點為數組最大值,分左右區間構造
    • 迭代:比較複雜,意義不大
    • 遞歸:前序,同時操作兩個樹的節點,注意合併的規則
    • 迭代:使用隊列,類似層序遍歷

求二叉搜索樹的屬性

    • 遞歸:二叉搜索樹的遞歸是有方向的
    • 迭代:因為有方向,所以迭代法很簡單
    • 遞歸:中序,相當於變成了判斷一個序列是不是遞增的
    • 迭代:模擬中序,邏輯相同
    • 遞歸:中序,雙指針操作
    • 迭代:模擬中序,邏輯相同
    • 遞歸:中序,清空結果集的技巧,遍歷一遍便可求眾數集合
    • 迭代:模擬中序,邏輯相同
    • 遞歸:中序,雙指針操作累加
    • 迭代:模擬中序,邏輯相同

二叉樹公共祖先問題

    • 遞歸:後序,回溯,找到左子樹出現目標值,右子樹節點目標值的節點。
    • 迭代:不適合模擬回溯
    • 遞歸:順序無所謂,如果節點的數值在目標區間就是最近公共祖先
    • 迭代:按序遍歷

二叉搜索樹的修改與構造

    • 遞歸:順序無所謂,通過遞歸函數返回值添加節點
    • 迭代:按序遍歷,需要記錄插入父節點,這樣才能做插入操作
    • 遞歸:前序,想清楚刪除非葉子節點的情況
    • 迭代:有序遍歷,較複雜
    • 遞歸:前序,通過遞歸函數返回值刪除節點
    • 迭代:有序遍歷,較複雜
    • 遞歸:前序,數組中間節點分割
    • 迭代:較複雜,通過三個隊列來模擬

階段總結

大家以上題目都做過了,也一定要看如下階段小結。

「每周小結都會對大家的疑問做統一解答,並且對每周的內容進行拓展和補充,所以一定要看,將細碎知識點一網打盡!」

最後總結

「在二叉樹題目選擇什麼遍歷順序是不少同學頭疼的事情,我們做了這麼多二叉樹的題目了,Carl給大家大體分分類」

  • 涉及到二叉樹的構造,無論普通二叉樹還是二叉搜索樹一定前序,都是先構造中節點。
  • 求普通二叉樹的屬性,一般是後序,一般要通過遞歸函數的返回值做計算。
  • 求二叉搜索樹的屬性,一定是中序了,要不白瞎了有序性了。

注意在普通二叉樹的屬性中,我用的是一般為後序,例如單純求深度就用前序, 二叉樹:找所有路徑也用了前序,這是為了方便讓父節點指向子節點。

所以求普通二叉樹的屬性還是要具體問題具體分析。

「最後,二叉樹系列就這麼完美結束了,估計這應該是最長的系列了,感謝大家33天的堅持與陪伴,接下來我們又要開始新的系列了「回溯算法」!」

錄友們打卡的時候也說一說自己的感想吧!哈哈」

-------end-------

我將算法學習相關的資料已經整理到了

Github :https://github.com/youngyangyang04/leetcode-master,裡面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖,可以fork到自己倉庫有空看一看一定會有所收穫,順便給一個star支持一下吧!

我是程式設計師Carl,哈工大師兄,先後在騰訊和百度打雜,這裡每天8:35準時推送一道經典算法題目,我選擇的每道題目都不是孤立的,而是由淺入深,環環相扣,幫你梳理算法知識脈絡,輕鬆學算法!

期待你的關注

相關焦點

  • 網際網路公司高頻面試題目:構造一棵二叉搜索樹
    本題中,一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。在 和 中其實已經講過了,如果根據數組構造一顆二叉樹。「本質就是尋找分割點,分割點作為當前節點,然後遞歸左區間和右區間」。
  • 網際網路公司高頻面試題目「回溯算法」求子集問題(二)
    nums,返回該數組所有可能的子集(冪集)。這道題目和區別就是集合裡有重複元素了,而且求取的子集要去重。用示例中的[1, 2, 2] 來舉例,如圖所示:(「注意去重需要先對集合排序」)本題就是其實就是的基礎上加上了去重,去重我們在回溯算法:求組合總和(三)也講過了,所以我就直接給出代碼了:C++代碼class
  • 網際網路公司高頻面試題目:如何把二叉搜索樹轉成累加樹
    >給出二叉 搜索 樹的根節點,該樹的節點值各不相同,請你將其轉換為累加樹(Greater Sum Tree),使每個節點 node 的新值等於原樹中大於或等於 node.val 的值之和。那麼知道如何遍歷這個二叉樹,也就迎刃而解了,「從樹中可以看出累加的順序是右中左,所以我們需要反中序遍歷這個二叉樹,然後順序累加就可以了」。
  • 網際網路公司面試題目之哈希表總結篇!(每逢總結必經典)
    這道題目包含小寫字母,那麼使用數組來做哈希最合適不過。在中同樣要求只有小寫字母,那麼就給我們濃濃的暗示,用數組!本題和很像,是求 字符串a 和 字符串b 是否可以相互組成,在中是求字符串a能否組成字符串b,而不用管字符串b 能不能組成字符串a。一些同學可能想,用數組幹啥,都用map不就完事了。
  • 一文學會哈希法解題(leetcode哈希表面試高頻題目總結)
    注意題目特意說明:輸出結果中的每個元素一定是唯一的,也就是說輸出的結果的去重的, 同時可以不考慮輸出結果的順序。這道題用暴力的解法時間複雜度是O(n^2),這種解法面試官一定不會滿意,那我們看看使用哈希法進一步優化。
  • 網際網路算法崗面試常見100題精析-題目剖析、解題思路、代碼分析
    關於本書 本書目前共整理了105道 高頻面試算法題目,全部採用漫畫圖解的方式。因為在每道題目中,我都會儘量去串基礎知識,以達到學以致用的效果。 學完本教程期望達到什麼樣的目的 掌握基本的數據結構與算法 掌握各類型高頻面試算法題 本教程有何特色 每一道算法題都配有完整圖解!僅此一家! 題解是圍繞什麼編寫的 掌握!
  • 經典面試題目本周小結!(回溯算法系列一)
    周二在 中,我們開始用回溯法解決第一道題目,組合問題。整體思路還是一樣的,本題的剪枝會好想一些,即:「已選元素總和如果已經大於n(題中要求的和)了,那麼往後遍歷就沒有意義了,直接剪掉」。如果大家在現場面試的時候,一定要注意各種輸入異常的情況,例如本題輸入1 * #按鍵。其實本題不算難,但也處處是細節,還是要反覆琢磨。
  • 網際網路公司高頻面試題目「回溯算法」:求組合總和II
    說明:所有數字(包括目標數)都是正整數。解集不能包含重複的組合。「本題的難點在於區別2中:集合(數組candidates)有重複元素,但還不能有重複的組合」。一些同學可能想了:我把所有組合求出來,再用set或者map去重,這麼做很容易超時!
  • 2020年安徽教師資格考試面試題目
    2020年安徽教師資格考試面試題目由NTCE考試快訊提供,以及提供2020安徽教師資格試題真題考試信息。更多關於2020年安徽教師資格考試面試題目,安徽教師資格試講,安徽教師資格面試,教師資格結構化試題快訊的內容,請關注安徽教師資格考試網!!
  • 網際網路公司高頻面試題目「回溯算法」:分割回文串
    )切割到字符串的結尾位置,說明找到了一個切割方法。(這兩個參數可以放到函數參數裡)本題遞歸函數參數還需要startIndex,因為切割過的地方,不能重複切割,和組合問題也是保持一致的。在 中我們深入探討了組合問題什麼時候需要startIndex,什麼時候不需要startIndex。
  • 「力扣」鍊表經典面試題目大總結!(每逢總結必經典)
    反轉鍊表是面試中高頻題目,很考察面試者對鍊表操作的熟練程度。我在文章中,給出了兩種反轉的方式,迭代法和遞歸法。建議大家先學透迭代法,然後再看遞歸法,因為遞歸法比較繞,如果迭代還寫不明白,遞歸基本也寫不明白了。
  • 網際網路公司高頻面試題目「回溯算法」遞增子序列
    這又是子集,又是去重,是不是不由自主的想起了剛剛講過的。就是因為太像了,更要注意差別所在,要不就掉坑裡了!在中我們是通過排序,再加一個標記數組來達到去重的目的。而本題求自增子序列,是不能對原數組進行排序的,排完序的數組都是自增子序列了。
  • 2020年史上最全最新阿里1000道Java面試題目大匯總(強烈建議收藏)
    這篇文章主要介紹了史上最全阿里1000道Java面試題目大匯總,小編覺得挺不錯的,現在分享給大家,也給大家做個參考一起跟隨小編過來看看吧,文末附面試答案,及阿里、騰訊、字節、美團等大廠的高頻面試資料及其他高頻面試資料。一:阿里技術一面(基礎掌握牢固)常用的異常類型?
  • NTCE2020年安徽教師資格面試題目解析
    2020年安徽教師資格面試題目解析由NTCE考試快訊提供,以及提供2020安徽中小學教師資格證試題真題考試信息。更多關於2020年安徽教師資格面試題目解析,教師資格結構化試題,安徽教師資格面試,安徽教師資格試講快訊的內容,請關注安徽中小學教師資格證考試網!!
  • 網際網路公司高頻面試題目:「回溯算法」電話號碼的字母組合
    給出數字到字母的映射如下(與電話按鍵相同)。注意 1 不對應任何字母。再來看參數,參數指定是有題目中給的string digits,然後還要有一個參數就是int型的index。注意這個index可不是 和中的startIndex了。這個index是記錄遍歷第幾個數字了,就是用來遍歷digits的(題目中給出數字字符串),同時index也表示樹的深度。
  • 阿里Java面試題目大匯總(強烈建議收藏)
    這篇文章主要介紹了史上最全阿里Java面試題目大匯總,提莫覺得挺不錯的,現在分享給大家,也給大家做個參考。一起跟隨提莫過來看看吧如果你看完覺得能算不錯的話!可以用發財的小手點點讚☺!Thread的 notify()給notifyAll()的區別?notifiy()是喚醒的那一個線程?Thread.sleep()喚醒以後是否需要重新競爭?單例有多少種寫法? 有什麼區別? 你常用哪一種單例,為什麼用這種?問一個Thread.join()相關的問題?寫一個JAVA死鎖的列子?
  • (二叉樹系列四)
    這已經是二叉樹的第四周總結了,二叉樹是非常重要的數據結構,也是面試中的常客,所以有必要一步一步幫助大家徹底掌握二叉樹!其實套路是一樣,只不過一起操作兩個樹的指針,我們之前講過求 二叉樹:我對稱麼?的時候,已經初步涉及到了 一起遍歷兩顆二叉樹了。
  • 網際網路高頻面試題目:「回溯算法」求組合總和
    本題k相當於了樹的深度,9(因為整個集合就是9個數)就是樹的寬度。例如 k = 2,n = 4的話,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(個數) = 2, n(和) = 4的組合。)目標和,也就是題目中的n。
  • 騰訊面試題目「回溯算法」排列問題(二)
    -10 <= nums[i] <= 10思路這道題目和的區別在於我以示例中的 [1,1,2]為例 (為了方便舉例,已經排序)抽象為一棵樹,去重過程如圖:圖中我們對同一樹層,前一位(也就是nums[i-1])如果使用過,那麼就進行去重。
  • 2020年安徽教師資格考試面試題目-中小學教師資格證網
    2020年安徽教師資格考試面試題目由中小學教師資格證網考試快訊提供,以及提供2020安徽教師資格試題真題考試信息。更多關於2020年安徽教師資格考試面試題目,教師資格結構化試題,安徽教師資格試講,安徽教師資格面試快訊的內容,請關注安徽教師資格考試網!!