[[397667]]

這假期咋就唰的一下就沒(méi)啦，昨天還跟放假第一天似的，今天就開(kāi)始上班了。

既然開(kāi)工了，那咱們就隨遇而安唄，繼續(xù)努力搬磚吧。

下面我們將鏡頭切到袁記菜館。

小二：掌柜的，最近大家都在忙著種樹(shù)，說(shuō)是要保護(hù)環(huán)境。

老板娘：樹(shù) ? 咱們店有呀，前幾年種的那棵葡萄樹(shù)，不是都結(jié)果子了嗎?就數(shù)你吃的最多。

小兒：這.......。

大家應(yīng)該猜到，咱們今天要嘮啥了。

之前給大家介紹了鏈表,棧，哈希表 等數(shù)據(jù)結(jié)構(gòu)

今天咱們來(lái)看一種新的數(shù)據(jù)結(jié)構(gòu)，樹(shù)。

PS：本篇文章內(nèi)容較基礎(chǔ)，對(duì)于沒(méi)有學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)會(huì)有一些幫助，如果你已經(jīng)學(xué)過(guò)的話，也可以復(fù)習(xí)一下，查缺補(bǔ)漏，后面會(huì)繼續(xù)更新這個(gè)系列。

本文大綱

本文大綱

注：可能有的同學(xué)不喜歡手機(jī)閱讀，所以將這篇同步在了我的倉(cāng)庫(kù)，大家可以去 Github 進(jìn)行閱讀，點(diǎn)擊文章最下方的閱讀原文即可

樹(shù)

我們先來(lái)看下百度百科對(duì)樹(shù)的定義

樹(shù)是 n (n >= 0) 個(gè)節(jié)點(diǎn)的有限集。n = 0 時(shí) 我們稱之為空樹(shù), 空樹(shù)是樹(shù)的特例。

在任意一棵非空樹(shù)中：

• 有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根(Root)的節(jié)點(diǎn)
• 當(dāng) n > 1 時(shí)，其余節(jié)點(diǎn)可分為 m (m > 0)個(gè)互不相交的有限集 T1、T2、........Tm，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)。

我們一起來(lái)拆解一下上面的兩句話，到底什么是子樹(shù)呢?見(jiàn)下圖

樹(shù)

例如在上面的圖中

有且僅有一個(gè)特定的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，也就是上圖中的橙色節(jié)點(diǎn)。

當(dāng)節(jié)點(diǎn)數(shù)目大于 1 時(shí)，除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集 T1,T2........Tm。

例如上圖中，我們將根節(jié)點(diǎn)以外的節(jié)點(diǎn)，分為了 T1 (2，3，4，5，6，7)，T2(8，9)兩個(gè)有限集。

那么 T1 (綠色節(jié)點(diǎn))和 T2(藍(lán)色節(jié)點(diǎn))就是根節(jié)點(diǎn)(橙色節(jié)點(diǎn))的子樹(shù)。

我們拆解之后發(fā)現(xiàn)，我們上圖中的例子符合樹(shù)的要求，另外不知道大家有沒(méi)有注意到這個(gè)地方。

除根節(jié)點(diǎn)以外的節(jié)點(diǎn)，可分為 m 個(gè)互不相交的有限集。

那么這個(gè)互不相交又是什么含義呢?見(jiàn)下圖。

我們將 (A) , (B) , (C) , (D) 代入上方定義中發(fā)現(xiàn)，(A) , (B) 符合樹(shù)的定義，(C), (D) 不符合，這是因?yàn)?(C) , (D) 它們都有相交的子樹(shù)。

好啦，到這里我們知道如何辨別樹(shù)啦，下面我們通過(guò)下面兩張圖再來(lái)深入了解一下樹(shù)。

主要從節(jié)點(diǎn)類型，節(jié)點(diǎn)間的關(guān)系下手。

這里節(jié)點(diǎn)的高度和深度

可能容易記混，我們代入到現(xiàn)實(shí)即可。

我們求物體深度時(shí)，從上往下測(cè)量，求高度時(shí)，從下往上測(cè)量，節(jié)點(diǎn)的高度和深度也是如此。

二叉樹(shù)

我們刷題時(shí)遇到的就是二叉樹(shù)啦，下面我們一起來(lái)了解一下二叉樹(shù)

二叉樹(shù)前提是一棵樹(shù)，也就是需要滿足我們樹(shù)的定義的同時(shí)，還需要滿足以下要求

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

注意我們這里提到的是最多，所以二叉樹(shù)并不是必須要求每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，也可以有的僅有一個(gè)左子節(jié)點(diǎn)，有的節(jié)點(diǎn)僅有一個(gè)右子節(jié)點(diǎn)。

下面我們來(lái)總結(jié)一下二叉樹(shù)的特點(diǎn)

• 每個(gè)節(jié)點(diǎn)最多有兩棵子樹(shù)，也就是說(shuō)二叉樹(shù)中不存在度大于 2 的節(jié)點(diǎn)，節(jié)點(diǎn)的度可以為 0，1，2。
• 左子樹(shù)和右子樹(shù)是有順序的,有左右之分。
• 假如只有一棵子樹(shù) ，也要區(qū)分它是左子樹(shù)還是右子樹(shù)

好啦，我們已經(jīng)了解了二叉樹(shù)的特點(diǎn)，那我們分析一下，下圖中的樹(shù)是否滿足二叉樹(shù)定義，共有幾種二叉樹(shù)。

上圖共為 5 種不同的二叉樹(shù)，在二叉樹(shù)的定義中提到，二叉樹(shù)的左子樹(shù)和右子樹(shù)是有順序的，所以 B，C 是兩個(gè)不同的二叉樹(shù)，故上圖為 5 種不同的二叉樹(shù)。

特殊的二叉樹(shù)

下面我們來(lái)說(shuō)幾種比較特殊的二叉樹(shù)，可以幫助我們刷題時(shí)，考慮到特殊情況。

滿二叉樹(shù)

滿二叉樹(shù)：在一棵二叉樹(shù)中，所有分支節(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有的葉子都在同一層,這種樹(shù)我們稱之為滿二叉樹(shù).見(jiàn)下圖

我們發(fā)現(xiàn)只有 (B) 符合滿二叉樹(shù)的定義,我們發(fā)現(xiàn)其實(shí)滿二叉樹(shù)也為完全二叉樹(shù)的一種。

完全二叉樹(shù)

完全二叉樹(shù)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹(shù)的左部。

哦!我們可以這樣理解，除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，而且最后一層的葉子節(jié)點(diǎn)必須靠左。

下面我們來(lái)看一下這幾個(gè)例子

上面的幾個(gè)例子中，(A)(B)為完全二叉樹(shù)，(C)(D)不是完全二叉樹(shù)

斜二叉樹(shù)

這個(gè)就很好理解啦,斜二叉樹(shù)也就是斜的二叉樹(shù),所有的節(jié)點(diǎn)只有左子樹(shù)的稱為左斜樹(shù),所有節(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)稱為右斜樹(shù).

諾,下面這倆就是.

另外還有 一些二叉樹(shù)的性質(zhì), 比如第 i 層至多有多少節(jié)點(diǎn),通過(guò)葉子節(jié)點(diǎn)求度為 2 的節(jié)點(diǎn), 通過(guò)節(jié)點(diǎn)樹(shù)求二叉樹(shù)的深度等, 這些是考研?？嫉闹R(shí), 就不在這里進(jìn)行贅述,需要的同學(xué)可以看一下王道或者天勤的數(shù)據(jù)結(jié)構(gòu), 上面描述的很具體, 并附有證明過(guò)程.

好啦，我們已經(jīng)了解了二叉樹(shù)，那么二叉樹(shù)如何存儲(chǔ)呢?

如何存儲(chǔ)二叉樹(shù)

二叉樹(shù)多采用兩種方法進(jìn)行存儲(chǔ),基于數(shù)組的順序存儲(chǔ)法和基于指針的二叉鏈?zhǔn)酱鎯?chǔ)法

這里我們?cè)賮?lái)回顧一下如何用數(shù)組存儲(chǔ)完全二叉樹(shù).

我們首先看根節(jié)點(diǎn)，也就是值為 1 的節(jié)點(diǎn)，它在數(shù)組中的下標(biāo)為 1 ,它的左子節(jié)點(diǎn)，也就是值為 4 的節(jié)點(diǎn)，此時(shí)索引為 2，右子節(jié)點(diǎn)也就是值為 2 的節(jié)點(diǎn)，它的索引為 3。

我們發(fā)現(xiàn)其中的關(guān)系了嗎?

數(shù)組中，某節(jié)點(diǎn)(非葉子節(jié)點(diǎn))的下標(biāo)為 i , 那么其左子節(jié)點(diǎn)下標(biāo)為 2*i(這里可以直接通過(guò)相乘得到左孩子, 也就是為什么空出第一個(gè)位置, 如果從 0 開(kāi)始存，則需要 2i+1 才行), 右子節(jié)點(diǎn)為 2i+1，其父節(jié)點(diǎn)為 i/2 。既然我們完全可以根據(jù)索引找到某節(jié)點(diǎn)的 左子節(jié)點(diǎn) 和右子節(jié)點(diǎn)，那么我們用數(shù)組存儲(chǔ)是完全沒(méi)有問(wèn)題的。

但是,我們?cè)倏紤]一下這種情景,如果我們用數(shù)組存儲(chǔ)斜樹(shù)時(shí)會(huì)出現(xiàn)什么情況?

通過(guò) 2*i 進(jìn)行存儲(chǔ)左子節(jié)點(diǎn)的話,如果遇到斜樹(shù)時(shí),則會(huì)浪費(fèi)很多的存儲(chǔ)空間,這樣顯然是不合適的,

所以說(shuō)當(dāng)存儲(chǔ)完全二叉樹(shù)時(shí),我們用數(shù)組存儲(chǔ),無(wú)疑是最省內(nèi)存的，但是存儲(chǔ)斜樹(shù)時(shí)，則就不太合適。

所以我們下面介紹一下另一種存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).

因?yàn)槎鏄?shù)的每個(gè)節(jié)點(diǎn), 最多有兩個(gè)孩子, 所以我們只需為每個(gè)節(jié)點(diǎn)定義一個(gè)數(shù)據(jù)域,兩個(gè)指針域即可

val 為節(jié)點(diǎn)的值, left 指向左子節(jié)點(diǎn), right 指向右子節(jié)點(diǎn)。

下面我們對(duì)樹(shù) 1, 2, 3, 4, 5, 6, 7 使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ),即為下面這種情況。

二叉鏈表的節(jié)點(diǎn)結(jié)構(gòu)定義代碼

public class BinaryTree { 
    int val; 
    BinaryTree left; 
    BinaryTree right; 
    BinaryTree() {} 
    BinaryTree(int val) { this.val = val; } 
    BinaryTree(int val, BinaryTree left, BinaryTree right) { 
        this.val = val; 
        this.left = left; 
        this.right = right; 
    } 
} 

另外我們?cè)谒㈩}的時(shí)候, 可以自己實(shí)現(xiàn)一下數(shù)據(jù)結(jié)構(gòu), 加深我們的理解, 提升基本功, 而且面試考的也越來(lái)越多.

好啦,下面我們說(shuō)一下樹(shù)的遍歷,

下面我會(huì)用動(dòng)圖的形式進(jìn)行描述,很容易理解, 我也會(huì)為大家總結(jié)對(duì)應(yīng)的題目,歡迎各位閱讀.

遍歷二叉樹(shù)

二叉樹(shù)的遍歷指從根節(jié)點(diǎn)出發(fā),按照某種次序依次訪問(wèn)二叉樹(shù)的所有節(jié)點(diǎn),使得每個(gè)節(jié)點(diǎn)都被訪問(wèn)且訪問(wèn)一次.

我們下面介紹二叉樹(shù)的幾種遍歷方法及其對(duì)應(yīng)的題目, 前序遍歷, 中序遍歷 , 后序遍歷 , 層序遍歷 .

前序遍歷

前序遍歷的順序是, 對(duì)于樹(shù)中的某節(jié)點(diǎn),先遍歷該節(jié)點(diǎn),然后再遍歷其左子樹(shù),最后遍歷其右子樹(shù).

只看文字有點(diǎn)生硬, 下面我們直接看動(dòng)畫(huà)吧

前序遍歷

測(cè)試題目: leetcode 144. 二叉樹(shù)的前序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution { 
    public List<Integer> preorderTraversal(TreeNode root) { 
        List<Integer> arr = new ArrayList<>(); 
        preorder(root,arr); 
        return arr; 
 
    } 
    public void preorder(TreeNode root,List<Integer> arr) { 
        if (root == null) { 
            return; 
        } 
        arr.add(root.val); 
        preorder(root.left,arr); 
        preorder(root.right,arr); 
    } 
} 

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n) 為遞歸過(guò)程中棧的開(kāi)銷(xiāo),平均為 O(logn),但是當(dāng)二叉樹(shù)為斜樹(shù)時(shí)則為 O(n)

為了控制文章篇幅, 二叉樹(shù)的迭代遍歷形式, 會(huì)在下篇文章進(jìn)行介紹。

中序遍歷

中序遍歷的順序是, 對(duì)于樹(shù)中的某節(jié)點(diǎn),先遍歷該節(jié)點(diǎn)的左子樹(shù), 然后再遍歷該節(jié)點(diǎn), 最后遍歷其右子樹(shù)

繼續(xù)看動(dòng)畫(huà)吧, 如果有些遺忘或者剛開(kāi)始學(xué)數(shù)據(jù)結(jié)構(gòu)的同學(xué)可以自己模擬一下執(zhí)行步驟.

中序遍歷

測(cè)試題目: leetcode 94 題 二叉樹(shù)的中序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution { 
    public List<Integer> inorderTraversal(TreeNode root) { 
          
         List<Integer> res = new ArrayList<>(); 
         inorder(root, res); 
         return res; 
 
    } 
    public void inorder (TreeNode root, List<Integer> res) { 
        if (root == null) { 
            return; 
        } 
        inorder(root.left, res); 
        res.add(root.val); 
        inorder(root.right, res); 
 
    } 
} 

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n)

后序遍歷

后序遍歷的順序是,對(duì)于樹(shù)中的某節(jié)點(diǎn), 先遍歷該節(jié)點(diǎn)的左子樹(shù), 再遍歷其右子樹(shù), 最后遍歷該節(jié)點(diǎn).

哈哈,繼續(xù)看動(dòng)畫(huà)吧,看完動(dòng)畫(huà)就懂啦.

后序遍歷

測(cè)試題目: leetcode 145 題 二叉樹(shù)的后序遍歷

代碼實(shí)現(xiàn)(遞歸版)

class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
         List<Integer> res = new ArrayList<>(); 
         postorder(root,res); 
         return res; 
    } 
 
    public void postorder(TreeNode root, List<Integer> res) { 
        if (root == null) { 
            return; 
        } 
        postorder(root.left, res); 
        postorder(root.right, res); 
        res.add(root.val); 
    } 
} 

時(shí)間復(fù)雜度 : O(n) 空間復(fù)雜度 : O(n)

層序遍歷

顧名思義,一層一層的遍歷.

比如剛才那棵二叉樹(shù)的層序遍歷序列即為 1 ~ 9.

二叉樹(shù)的層序, 這里我們需要借助其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn), 我們思考一下, 我們需要對(duì)二叉樹(shù)進(jìn)行層次遍歷, 從上往下進(jìn)行遍歷, 我們可以借助什么數(shù)據(jù)結(jié)構(gòu)來(lái)幫我們呢 ?

我們可以利用隊(duì)列先進(jìn)先出的特性，使用隊(duì)列來(lái)幫助我們完成層序遍歷, 具體操作如下

讓二叉樹(shù)的每一層入隊(duì), 然后再依次執(zhí)行出隊(duì)操作,

對(duì)該層節(jié)點(diǎn)執(zhí)行出隊(duì)操作時(shí), 需要將該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)進(jìn)行入隊(duì)操作,

這樣當(dāng)該層的所有節(jié)點(diǎn)出隊(duì)結(jié)束后, 下一層也就入隊(duì)完畢,

不過(guò)我們需要考慮的就是, 我們需要通過(guò)一個(gè)變量來(lái)保存每一層節(jié)點(diǎn)的數(shù)量.

這樣做是為了防止, 一直執(zhí)行出隊(duì)操作, 使輸出不能分層

好啦,下面我們直接看動(dòng)畫(huà)吧,

測(cè)試題目: leetcode 102 二叉樹(shù)的層序遍歷

題目代碼

class Solution { 
    public List<List<Integer>> levelOrder(TreeNode root) { 
     
      List<List<Integer>> res = new ArrayList<>(); 
      if (root == null) { 
          return res; 
      }  
      //入隊(duì) root 節(jié)點(diǎn)，也就是第一層   
      Queue<TreeNode> queue = new LinkedList<>(); 
      queue.offer(root); 
      while (!queue.isEmpty()) { 
          List<Integer> list = new ArrayList<>(); 
          int size = queue.size(); 
          for (int i = 0; i < size; ++i) { 
              TreeNode temp = queue.poll(); 
              //孩子節(jié)點(diǎn)不為空，則入隊(duì) 
              if (temp.left != null)  queue.offer(temp.left); 
              if (temp.right != null) queue.offer(temp.right); 
              list.add(temp.val); 
          } 
          res.add(list); 
      } 
      return res; 
    } 
} 

時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)

大家如果吃透了二叉樹(shù)的層序遍歷的話，可以順手把下面幾道題目解決掉，思路一致，甚至都不用拐彎

• leetcode 107. 二叉樹(shù)的層序遍歷 II
• leetcode 103. 二叉樹(shù)的鋸齒形層序遍歷

上面兩道題僅僅是多了翻轉(zhuǎn)

• leetcode 199. 二叉樹(shù)的右視圖
• leetcode 515. 在每個(gè)樹(shù)行中找最大值
• leetcode 637. 二叉樹(shù)的層平均值

這三道題，僅僅是加了一層的一些操作

• leetcode 116 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)
• leetcode 117 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)2

這兩個(gè)題對(duì)每一層的節(jié)點(diǎn)進(jìn)行鏈接即可，兩道題目代碼一致

大家可以去順手解決這些題目，但是也要注意一下其他解法，把題目吃透。不要為了數(shù)目而刷題，好啦，今天的節(jié)目就到這里啦，我們下期見(jiàn)!

本文轉(zhuǎn)載自微信公眾號(hào)「袁廚的算法小屋」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系袁廚的算法小屋公眾號(hào)。