天天看點

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

01PART

二叉樹是啥

二叉樹有多重要?單就面試而言,在 leetcode 中二叉樹相關的題目占據了300多道,近三分之一。同時,二叉樹在整個算法闆塊中還起到承上啟下的作用:不但是數組和連結清單的延伸,又可以作為圖的基礎。總之,非常重要!

什麼是二叉樹?官方是這樣定義的:

在計算機科學中,二叉樹是每個結點最多有兩個子樹的樹結構

。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

上面那是個玩笑,二叉樹長這樣:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

二叉樹常被用于實作

二叉查找樹

二叉堆

。樹比連結清單稍微複雜,因為連結清單是線性資料結構,而樹不是。樹的問題很多都可以由廣度優先搜尋或深度優先搜尋解決。

一般而言,我們會看到下面這些與樹相關的術語:

與樹相關的術語

樹的結點(node):包含一個資料元素及若幹指向子樹的分支;

孩子結點(child node):結點的子樹的根稱為該結點的孩子;

雙親結點:B 結點是A 結點的孩子,則A結點是B 結點的雙親;

兄弟結點:同一雙親的孩子結點;堂兄結點:同一層上結點;

祖先結點: 從根到該結點的所經分支上的所有結點

子孫結點:以某結點為根的子樹中任一結點都稱為該結點的子孫

結點層:根結點的層定義為1;根的孩子為第二層結點,依此類推;

樹的深度:樹中最大的結點層

結點的度:結點子樹的個數

樹的度:樹中最大的結點度。

葉子結點:也叫終端結點,是度為 0 的結點;

分枝結點:度不為0的結點;

有序樹:子樹有序的樹,比如家族樹;

無序樹:不考慮子樹的順序;

了解了上面的基本概念之後。我們将通過幾道例題,為大家引入樹的經典操作。

02PART

二叉樹最大深度

複習上面的概念:樹的深度指的是樹中最大的結點層。

第104題:給定一個二叉樹,找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例:

給定二叉樹 [3,9,20,null,null,15,7],

3
   / 
  9  20
    /  
   15   7
           

基本概念掌握:

每個節點的深度與它左右子樹的深度有關,且等于其左右子樹最大深度值加上 1。

即:

maxDepth(root) = max(maxDepth(root.left),maxDepth(root.right)) + 1

以 [3,9,20,null,null,15,7] 為例:

  • 我們要對根節點的最大深度求解,就要對其左右子樹的深度進行求解
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
  • 我們看出。以4為根節點的子樹沒有左右節點,其深度為1。而以20為根節點的子樹的深度,同樣取決于它的左右子樹深度。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
  • 對于15和7的子樹,我們可以一眼看出其深度為1。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
  • 由此我們可以得到根節點的最大深度為
maxDepth
           

根據分析,我們通過

遞歸

進行求解:

1
           

其實我們上面用的遞歸方式,本質上是使用了DFS的思想。是以這裡就可以引出什麼是DFS:深度優先搜尋算法(Depth First Search),

對于二叉樹而言

它沿着樹的深度周遊樹的節點,盡可能深的搜尋樹的分支,這一過程一直進行到已發現從源節點可達的所有節點為止。

( 注意,這裡的前提是對二叉樹而言。DFS本身作為圖算法的一種,在後續我會單獨拉出來和回溯放一起講。)

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

如上圖二叉樹,它的通路順序為:

A-B-D-E-C-F-G

到這裡,我們思考一個問題?雖然我們用遞歸的方式根據DFS的思想順利完成了題目。但是這種方式的缺點卻顯而易見。因為

在遞歸中,如果層級過深,我們很可能儲存過多的臨時變量,導緻棧溢出

。這也是為什麼我們一般不在背景代碼中使用遞歸的原因。如果不了解,下面我們詳細說明:

事實上,函數調用的參數是通過棧空間來傳遞的,在調用過程中會

占用線程的棧資源

。而遞歸調用,

隻有走到最後的結束點後函數才能依次退出

,而未到達最後的結束點之前,占用的棧空間一直沒有釋放,如果遞歸調用次數過多,就可能導緻占用的棧資源超過線程的最大值,進而導緻棧溢出,導緻程式的異常退出。

是以,我們引出下面的話題:如何将遞歸的代碼轉化成非遞歸的形式。這裡請記住,

基本所有的遞歸轉非遞歸,都可以通過棧來進行實作

。非遞歸的DFS,代碼如下:

1
           

上面的代碼,唯一需要強調的是,為什麼需要先右後左壓入資料?是因為我們需要将先通路的資料,後壓入棧(請思考棧的特點)。

如果不了解代碼,請看下圖:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

說明:

  • 1:首先将a壓入棧
  • 2:a彈棧,将c、b壓入棧(注意順序)
  • 3:b彈棧,将e、d壓入棧
  • 4,5:d、e、c彈棧,将g、f壓入棧
  • 6:f、g彈棧

至此,非遞歸的 DFS 就講解完畢了。那如何通過非遞歸DFS的方式,來對本題求解呢?相信已經很簡單了,這個下去自己試試就ok了了。

03PART

二叉樹的層次周遊

在上文中,我們通過例題學習了二叉樹的DFS(深度優先搜尋),其實就是沿着一個方向一直向下周遊。那我們可不可以按照高度一層一層的通路樹中的資料呢?當然可以,就是本節中我們要講的BFS(寬度優先搜尋),同時也被稱為廣度優先搜尋。

第102題:給定一個二叉樹,傳回其按層次周遊的節點值。(即逐層地,從左到右通路所有節點)。

例如:

給定二叉樹: [3,9,20,null,null,15,7],

3
   
           

傳回其層次周遊結果:[[3],[9,20],[15,7]]

BFS,廣度/寬度優先。說白了就是

從上到下,先把每一層周遊完之後再周遊一下一層

。假如我們的樹如下:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

按照BFS,通路順序如下:

a->b->c->d->e->f->g

了解了BFS,我們開始對本題進行分析。同樣,我們先考慮本題的遞歸解法。想到遞歸,我們一般先想到DFS。我們可以對該二叉樹進行

先序周遊(根左右的順序)

,同時,記錄節點所在的層次level,并且對每一層都定義一個數組,然後将通路到的節點值放入對應層的數組中。

假設給定二叉樹為[3,9,20,null,null,15,7],圖解如下:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

根據分析,代碼如下:

1
           

上面的解法,其實相當于是用DFS的方法實作了二叉樹的BFS。那我們能不能直接使用BFS的方式進行解題呢?當然可以。我們使用Queue的資料結構。我們将root節點初始化進隊列,通過

消耗尾部,插入頭部

的方式來完成BFS。

具體步驟如下圖:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

根據分析,完成代碼:

1
           

04PART

二叉搜尋樹

BST是二叉搜尋樹,很重要。BST是二叉搜尋樹,很重要。BST是二叉搜尋樹,很重要。重要的事情說三遍。

第98題:給定一個二叉樹,判斷其是否是一個有效的二叉搜尋樹。

示例 1:

輸入:

5
   
           

輸出: false

解釋: 輸入為: [5,1,4,null,null,3,6]。

根節點的值為 5 ,但是其右子節點值為 4 。

要驗證二叉搜尋樹,首先得知道啥是二叉搜尋樹。二叉搜尋樹(Binary Search Tree),(又:二叉查找樹,二叉排序樹)它或者是

一棵空樹

,或者是具有下列性質的二叉樹:

若它的左子樹不空,則左子樹上所有結點的值均小于它的根結點的值;若它的右子樹不空,則右子樹上所有結點的值均大于它的根結點的值;它的左、右子樹也分别為二叉搜尋樹

這裡強調一下子樹的概念:設T是有根樹,a是T中的一個頂點,由a以及a的所有後裔(後代)導出的子圖稱為有向樹T的子樹。具體來說,

子樹就是樹的其中一個節點以及其下面的所有的節點所構成的樹

。比如下面這就是一顆二叉搜尋樹:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

下面這兩個都不是:

  • 圖中4節點位置的數值應該大于根節點
  • 圖中3節點位置的數值應該大于根節點
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

回到題目,那我們如何來驗證一顆二叉搜尋樹?首先看完題目,我們很容易想到 周遊整棵樹,比較所有節點,通過 左節點值<節點值,右節點值>節點值 的方式來進行求解。但是這種解法是錯誤的,因為

對于任意一個節點

,我們不光需要左節點值小于該節點,并且

左子樹上的所有節點值都需要小于該節點

。(右節點一緻)是以我們在此引入上界與下界,用以儲存之前的節點中出現的

最大值與最小值

代碼其實很簡單:

1
           

難就難在,可能大家看不懂這個遞歸!沒事,祭出大殺器:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

這裡需要強調的是,在每次遞歸中,我們除了

進行左右節點的校驗,還需要與上下界進行判斷

。其餘的就很簡單了。

05PART

BST的查找

在上文中,我們學習了二叉搜尋樹。那我們如何在二叉搜尋樹中查找一個元素呢?

第700題:給定二叉搜尋樹(BST)的根節點和一個值。你需要在BST中找到節點值等于給定值的節點。傳回以該節點為根的子樹。如果節點不存在,則傳回 NULL。

例如,給定二叉搜尋樹:

4
       
           

搜尋: 2

你應該傳回如下子樹:

2     
     
           

在上述示例中,如果要找的值是 5,但因為沒有節點值為 5,我們應該傳回 NULL。

先複習一下,

二叉搜尋樹

(BST)的特性:

1.若它的左子樹不為空,則所有左子樹上的值均小于其根節點的值 2.若它的右子樹不為空,則所有右子樹上的值均大于其根節點得值 3.它的左右子樹也分别為二叉搜尋樹

如下圖就是一棵典型的BST:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

現在我們來看題,假設目标值為 val。根據BST的特性,我們可以很容易想到查找過程(上面的驗證比查找稍難一點):

  • 如果val小于目前結點的值,轉向其左子樹繼續搜尋;
  • 如果val大于目前結點的值,轉向其右子樹繼續搜尋;
  • 如果已找到,則傳回目前結點。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

很簡單,不是嗎?然後我們可以給出疊代和遞歸兩種解法(給個Java的吧!):

1
           

06PART

BST的删除

查找有了,下面自然就要講删除。(為啥說我要着重墨在BST上面,因為BST這兩年在面試時非常高頻。面試官不可能說問你一個普通二叉樹的題目,要麼就是問堆,要麼就是問BST,或者就直接DFS考察回溯。)

第450題:給定一個二叉搜尋樹的根節點 root 和一個值 key,删除二叉搜尋樹中的 key 對應的節點,并保證二叉搜尋樹的性質不變。傳回二叉搜尋樹(有可能被更新)的根節點的引用。

一般來說,删除節點可分為兩個步驟:

首先找到需要删除的節點;

如果找到了,删除它。

說明:要求算法時間複雜度為 O(h),h 為樹的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

5
   / 
  3   6
 /    
2   4   7
           

給定需要删除的節點值是 3,是以我們首先找到 3 這個節點,然後删除它。

一個正确的答案是 [5,4,6,2,null,null,7], 如下圖所示。

5
   
           

另一個正确答案是 [5,2,6,null,4,null,7]。

5
   
           

如果你看到了這裡,相信肯定知道BST是個啥了。是以直接分析題目。我們要删除BST的一個節點,首先需要

找到該節點

。而找到之後,會出現三種情況。

  1. 待删除的節點左子樹為空,讓待删除節點的右子樹替代自己。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
  1. 待删除的節點右子樹為空,讓待删除節點的左子樹替代自己。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...
  1. 如果待删除的節點的左右子樹都不為空。我們需要找到 比目前節點小的最大節點(前驅) ,來替換自己
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

或者

比目前節點大的最小節點(後繼)

,來替換自己。

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

分析完畢,直接上代碼。這裡我們給出通過

後繼節點來替代自己

的方案(可以自行實作另一種方案):

1
           

07PART

平衡二叉樹

BST講解完了。上面也說了,别人考察我們肯定是考察特殊的。那二叉樹裡還有啥特殊的東東嘞?平衡二叉樹算是一個。

第110題:給定一個二叉樹,判斷它是否是高度平衡的二叉樹。

本題中,一棵高度平衡二叉樹定義為:

一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。

示例 1:

給定二叉樹 [3,9,20,null,null,15,7]

3
   / 
  9  20
    /  
   15   7
           

傳回 true 。

示例 2:

給定二叉樹 [1,2,2,3,3,null,null,4,4]

1
      
           

傳回 false 。

題其實是一道很簡單的題,主要是拿來複習一下高度。我們想判斷一棵樹是否滿足平衡二叉樹,無非就是判斷目前結點的兩個孩子是否滿足平衡,同時兩個孩子的高度差是否超過1。那

隻要我們可以得到高度,再基于高度進行判斷即可

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

這裡唯一要注意的是,當我們判定

其中任意一個節點如果不滿足平衡二叉樹時,那說明整棵樹已經不是一顆平衡二叉樹

,我們可以

對其進行阻斷,不需要繼續遞歸下去

然後還有一個初學者容易懵逼的:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

這玩意,并不是平衡二叉樹。上代碼:

1
           

08PART

完全二叉樹

還有啥特殊的,要撈出來講一講的?

第222題:給出一個完全二叉樹,求出該樹的節點個數。

說明:

完全二叉樹的定義如下:在完全二叉樹中,除了最底層節點可能沒填滿外,其餘每層節點數都達到最大值,并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層,則該層包含 1~ 2h 個節點。

示例:

輸入:

1
   
           

輸出: 6

老樣子,我們得說說啥是完全二叉樹。完全二叉樹由滿二叉樹引出,先來了解一下什麼是滿二叉樹。

如果二叉樹中除了葉子結點,每個結點的度都為 2,則此二叉樹稱為滿二叉樹。

(二叉樹的度代表某個結點的孩子或者說直接後繼的個數,這個在上面已經說過了。對于二叉樹而言,1度是隻有一個孩子或者說單子樹,2度是有兩個孩子或者說左右子樹都有。)

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

那什麼又是完全二叉樹呢:

如果二叉樹中除去最後一層節點為滿二叉樹,且最後一層的結點依次從左到右分布,則此二叉樹被稱為完全二叉樹

。比如下面這顆:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

這個就不是:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

上面做了這麼多題了,你應該能想到我要說啥 --- 遞歸。二叉樹的題目基本上都可以遞歸求解。

1func 
           

但是很明顯,出題者肯定不是要這種答案。因為

這種答案和完全二叉樹一毛錢關系都沒有

。是以我們繼續思考。

由于題中已經告訴我們這是一顆完全二叉樹,我們又已知了完全二叉樹除了最後一層,其他層都是滿的,并且最後一層的節點全部靠向了左邊。那我們可以想到,可以将該完全二叉樹可以分割成

若幹滿二叉樹和完全二叉樹

滿二叉樹直接根據層高h計算出節點為2^h-1,

然後

繼續計算子樹中完全二叉樹節點

。那如何分割成若幹滿二叉樹和完全二叉樹呢?

對任意一個子樹,周遊其左子樹層高left,右子樹層高right,相等左子樹則是滿二叉樹,否則右子樹是滿二叉樹

。這裡可能不容易了解,我們看圖。

假如我們有樹如下:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

我們看到根節點的左右子樹高度都為3,那麼說明左子樹是一顆滿二叉樹。因為節點已經填充到右子樹了,左子樹必定已經填滿了。是以左子樹的節點總數我們可以直接得到,是2^left - 1,加上目前這個root節點,則正好是2^3,即 8。然後隻需要再對右子樹進行遞歸統計即可。

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

那假如我們的樹是這樣:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

我們看到左子樹高度為3,右子樹高度為2。說明此時最後一層不滿,但倒數第二層已經滿了,可以直接得到右子樹的節點個數。同理,右子樹節點+root節點,總數為2^right,即2^2。再對左子樹進行遞歸查找。

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

根據分析,得出代碼:

1
           

09PART

二叉樹的剪枝

該講的都講了,突然想到忘了一個經典操作 - 剪枝。迅速補上!非常重要!這裡額外說一點,就本人而言,對這個操作以及其衍化形式的使用會比較頻繁。因為我是做反欺詐的,機器學習裡有一個概念叫做決策樹,那如果一顆決策樹完全生長,就會帶來比較大的過拟合問題。因為完全生長的決策樹,每個節點隻會包含一個樣本。是以我們就需要對決策樹進行剪枝操作,來提升整個決策模型的泛化能力... 聽不懂也沒關系,簡單點講,就是我覺得這個很重要,或者每道算法題都很重要。如果你在工作中沒有用到,不是說明算法不重要,而可能是你還不夠重要。

第814題:給定二叉樹根結點 root ,此外樹的每個結點的值要麼是 0,要麼是 1。傳回移除了所有不包含 1 的子樹的原二叉樹。

( 節點 X 的子樹為 X 本身,以及所有 X 的後代。)

示例1:

輸入: [1,null,0,0,1]

輸出: [1,null,0,null,1]

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

解釋:

隻有紅色節點滿足條件“所有不包含 1 的子樹”。

右圖為傳回的答案。

示例2:

輸入: [1,0,1,0,0,0,1]

輸出: [1,null,1,null,1]

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

示例3:

輸入: [1,1,0,1,1,0,1,0]

輸出: [1,1,0,1,1,null,1]

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

說明:

給定的二叉樹最多有 100 個節點。

每個節點的值隻會為 0 或 1 。

還是先解釋一下,啥是剪枝:假設有一棵樹,最上層的是root節點,而

父節點會依賴子節點

。如果現在有一些節點已經标記為無效,我們要删除這些無效節點。

如果無效節點的依賴的節點還有效,那麼不應該删除

,如果無效節點和它的子節點都無效,則可以删除。剪掉這些節點的過程,稱為剪枝,目的是

用來處理二叉樹模型中的依賴問題

說了好多遍了,二叉樹的問題,大多都可以通過遞歸進行求解。直接分析。假設我們有二叉樹如下:[0,1,0,1,0,0,0,0,1,1,0,1,0]:

長這樣:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

剪枝之後是這樣:

找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

剪什麼大家應該都能了解。那關鍵是怎麼剪?過程也很簡單,

在遞歸的過程中,如果目前結點的左右節點皆為空,且目前結點為0,我們就将目前節點剪掉即可。
找二叉樹中給定元素的的左孩子結點_萬字長文!二叉樹入門和刷題看這篇就夠了!...

其實很簡單,直接看代碼:

1func 
           

10PART

啰嗦一下

二叉樹入門整合系列篇到這裡就完事了,相信大家如果可以完整看完,一定會有所收獲。

繼續閱讀