「算法與數(shù)據(jù)結(jié)構(gòu)」二叉樹之美
前言
這次梳理的內(nèi)容是數(shù)據(jù)結(jié)構(gòu)專題中的「樹」，如果你看到樹這類數(shù)據(jù)結(jié)構(gòu)時(shí)，滿腦子頭疼，覺得它很難理解，如果是這樣子的話，那么本文可能對(duì)你或許有點(diǎn)幫助。
俗話說得好，要想掌握理解的話，我們得先了解它的概念，性質(zhì)等內(nèi)容。
圍繞以下幾個(gè)點(diǎn)來展開介紹樹👇
樹的基本概念
- 基本術(shù)語
- 樹的種類
- 二叉樹概念
- 二叉樹的遍歷
- 二叉樹題目匯總
腦圖👇
樹的基本概念
樹是用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合?；蛘吣憧梢园阉J(rèn)為是一種「抽象數(shù)據(jù)結(jié)構(gòu)」或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。
那么根據(jù)維基百科給出的定義，我們似乎可以這么理解：
它是由n(n>0)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無子節(jié)點(diǎn);
- 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn);
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn);
- 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹;
- 樹里面沒有環(huán)路(cycle)
這個(gè)時(shí)候，我們就需要拿出一張圖來看👇
從圖中來看，以上的五個(gè)特點(diǎn)都可以很好的總結(jié)出來
- A節(jié)點(diǎn)作為根節(jié)點(diǎn)，沒有父節(jié)點(diǎn)，所以是根節(jié)點(diǎn)。
- 除根節(jié)點(diǎn)(A)外，其他的節(jié)點(diǎn)都有父節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)只有有限個(gè)子節(jié)點(diǎn)或無子節(jié)點(diǎn)。
- 從某個(gè)節(jié)點(diǎn)開始，可以分為很多個(gè)子樹，舉個(gè)例子，從B節(jié)點(diǎn)開始，即是如此。
既然對(duì)樹有一定認(rèn)識(shí)后，我們需要了解它的一些術(shù)語。
基本術(shù)語
樹的基本術(shù)語
為了更加規(guī)范的總結(jié)，這里給出的描述來自于維基百科：
- 「節(jié)點(diǎn)的度」：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度;
- 「樹的度」：一棵樹中，最大的節(jié)點(diǎn)度稱為樹的度;
- 「葉節(jié)點(diǎn)」或「終端節(jié)點(diǎn)」：度為零的節(jié)點(diǎn);
- 「非終端節(jié)點(diǎn)」或「分支節(jié)點(diǎn)」：度不為零的節(jié)點(diǎn);
- 「父親節(jié)點(diǎn)」或「父節(jié)點(diǎn)」：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn);
- 「孩子節(jié)點(diǎn)」或「子節(jié)點(diǎn)」：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn);
- 「兄弟節(jié)點(diǎn)」：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn);
- 節(jié)點(diǎn)的「層次」：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推;
- 「深度」：對(duì)于任意節(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長，根的深度為0;
- 「高度」：對(duì)于任意節(jié)點(diǎn)n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0;
- 「堂兄弟節(jié)點(diǎn)」：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟;
- 「節(jié)點(diǎn)的祖先」：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn);
- 「子孫」：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫;
- 「森林」：由m(m>=0)棵互不相交的樹的集合稱為森林。
可以結(jié)合上述的圖來理解這些概念，通過兩者的結(jié)合，你一定會(huì)對(duì)樹有進(jìn)一步的了解的。
有以上基本概念，以及一些專業(yè)術(shù)語的掌握，接下來我們需要對(duì)樹進(jìn)行一個(gè)分類，看看樹有哪些種類。
樹的種類
理解了樹的概念以及基本術(shù)語，接下來，我們需要拓展的內(nèi)容就是樹的種類。
我們可以根據(jù)維基百科的依據(jù)來作為分類的標(biāo)準(zhǔn)👇
- 無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹;
- 有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹;
- 完全二叉樹：對(duì)于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹;
- 平衡二叉樹(AVL樹)：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于1的二叉樹;
- 排序二叉樹(英語：Binary Search Tree))：也稱二叉搜索樹、有序二叉樹;
- 滿二叉樹：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹;
- 二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹;
- 霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹;
- B樹：一種對(duì)讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多于兩個(gè)子樹。
既然樹的分類有這么多的話，那么我們是不是都需要一一掌握呢，我個(gè)人覺得，掌握二叉樹這種結(jié)構(gòu)就足夠了，它也是樹最簡單、應(yīng)用最廣泛的種類。
那么接下來，我們就來介紹一下二叉樹吧。
二叉樹的概念
二叉樹是一種典型的樹樹狀結(jié)構(gòu)。如它名字所描述的那樣，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)，通常子樹被稱作“左子樹”和“右子樹”。
二叉樹
從這個(gè)圖片的內(nèi)容來看，應(yīng)該很清楚的展示了二叉樹的結(jié)構(gòu)。
至于二叉樹的性質(zhì)的話，可以參考下圖，作為補(bǔ)充知識(shí)吧，個(gè)人覺得這個(gè)不是重點(diǎn)。
二叉樹的性質(zhì)
重點(diǎn)的話，我們需要掌握的應(yīng)該是它的遍歷方式。
二叉樹的遍歷
我們知道對(duì)于二叉樹的遍歷而言，有常見得三種遍歷方式，分別是以下三種：
- 前序遍歷
- 中序遍歷
- 后續(xù)遍歷
對(duì)于任何一種遍歷方式而言，我們不僅需要掌握它的非遞歸版本，同時(shí)對(duì)于它的遞歸版本來說，更是考察一個(gè)人的算法基本功，那么接下來，我們來看看吧。
前序遍歷
點(diǎn)擊這里，練習(xí)二叉樹的前序遍歷
給你二叉樹的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的 「前序」 遍歷。
假設(shè)我們mock一下假數(shù)據(jù)👇
- 輸入: [1,null,2,3]
- 1
- \
- 2
- /
- 3
- 輸出: [1,3,2]
那么根據(jù)我們對(duì)前序遍歷的理解，我們可以寫出解題偽代碼👇
- // TianTianUp
- // * function TreeNode(val, left, right) {
- // * this.val = (val===undefined ? 0 : val)
- // * this.left = (left===undefined ? null : left)
- // * this.right = (right===undefined ? null : right)
- // * }
- let inorderTraversal = (root, arr = []) => {
- if(root) {
- inorderTraversal(root.left, arr)
- arr.push(root.value)
- inorderTraversal(root.right, arr)
- }
- return arr
- }
非遞歸版本👇
對(duì)于非遞歸的話，我們需要借助一個(gè)數(shù)據(jù)結(jié)構(gòu)去存儲(chǔ)它的節(jié)點(diǎn)，需要使用的就是棧，它的思路可以借鑒👇
- 根節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，開始向它子節(jié)點(diǎn)遍歷
- 1.訪問目標(biāo)節(jié)點(diǎn)
- 2.左孩子入棧 -> 直至左孩子為空的節(jié)點(diǎn)
- 3.節(jié)點(diǎn)出棧，以右孩子為目標(biāo)節(jié)點(diǎn)，再依次執(zhí)行1、2、3
- let preorderTraversal = (root, arr = []) => {
- const stack = [], res = []
- let current = root
- while(current || stack.length > 0) {
- while (current) {
- res.push(current.val)
- stack.push(current)
- current = current.left
- }
- current = stack.pop()
- current = current.right
- }
- return res
- }
中序遍歷
給定一個(gè)二叉樹，返回它的中序 遍歷。
示例:
- 輸入: [1,null,2,3] 1
- 2 / 3
- 輸出: [1,3,2]
進(jìn)階: 遞歸算法很簡單，你可以通過迭代算法完成嗎?
遞歸版本👇
- const inorderTraversal = (root, arr = []) => {
- if(root) {
- inorderTraversal(root.left, arr)
- arr.push(root.val)
- inorderTraversal(root.right, arr)
- }
- return arr
- }
非遞歸版本，這里就不解釋了，跟前序遍歷一樣，思路一樣，用棧維護(hù)節(jié)點(diǎn)信息。
- const inorderTraversal = (root, arr = []) => {
- const stack = [], res = []
- let current = root
- while(current || stack.length > 0) {
- while (current) {
- stack.push(current)
- current = current.left
- }
- current = stack.pop()
- res.push(current.val)
- current = current.right
- }
- return res
- }
后續(xù)遍歷
給定一個(gè)二叉樹，返回它的 后序 遍歷。
示例:
- 輸入: [1,null,2,3]
- 1
- 2 / 3
- 輸出: [3,2,1]
進(jìn)階: 遞歸算法很簡單，你可以通過迭代算法完成嗎?
來源：力扣(LeetCode) 鏈接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
遞歸版本👇
- const postorderTraversal = (root, arr = []) => {
- if(root) {
- postorderTraversal(root.left, arr)
- postorderTraversal(root.right, arr)
- arr.push(root.val)
- }
- return arr
- }
非遞歸版本👇
其實(shí)，嗯，做完前面兩個(gè)后，會(huì)發(fā)現(xiàn)都是有套路滴~
- const postorderTraversal = (root, arr = []) => {
- const stack = [], res = []
- let current = root, last = null // last指針記錄上一個(gè)節(jié)點(diǎn)
- while(current || stack.length > 0) {
- while (current) {
- stack.push(current)
- current = current.left
- }
- current = stack[stack.length - 1]
- if (!current.right || current.right == last) {
- current = stack.pop()
- res.push(current.val)
- last = current
- current = null // 繼續(xù)彈棧
- } else {
- current = current.right
- }
- }
- return res
- }
二叉樹的層次遍歷 ⭐⭐
鏈接：二叉樹的層序遍歷
給你一個(gè)二叉樹，請(qǐng)你返回其按 「層序遍歷」 得到的節(jié)點(diǎn)值。(即逐層地，從左到右訪問所有節(jié)點(diǎn))。
示例：二叉樹：[3,9,20,null,null,15,7],
- 3
- /
- 9 20 /
- 15 7
返回其層次遍歷結(jié)果：
- [ [3], [9,20], [15,7] ]
來源：力扣(LeetCode) 鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
遞歸版本👇
- const levelOrder = function(root) {
- if(!root) return []
- let res = []
- dfs(root, 0, res)
- return res
- }
- function dfs(root, step, res){
- if(root){
- if(!res[step]) res[step] = []
- res[step].push(root.val)
- dfs(root.left, step + 1, res)
- dfs(root.right, step + 1, res)
- }
- }
非遞歸版本👇
這里借助的就是隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，先進(jìn)先出的機(jī)制。
- const levelOrder = (root) => {
- let queue = [], res = []
- if (root) queue.push(root);
- while (queue.length) {
- let next_queue = [],
- now_res = []
- while (queue.length) {
- root = queue.shift()
- now_res.push(root.val)
- root.left && next_queue.push(root.left)
- root.right && next_queue.push(root.right)
- }
- queue = next_queue
- res.push(now_res)
- }
- return res
- }
題目匯總
還是那句話，題目做不完的，剩下的就靠刷leetcode了，我還準(zhǔn)備了一些常見的二叉樹題集，題目的質(zhì)量還是不錯(cuò)的👇
- 二叉樹的最小深度⭐
- 二叉樹的最大深度⭐
- 相同的樹⭐
- 二叉搜索樹的范圍和⭐
- 對(duì)稱二叉樹⭐
- 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹⭐
- 二叉樹的層次遍歷 II⭐⭐
- 二叉樹的最近公共祖先⭐⭐
- 驗(yàn)證二叉搜索樹⭐⭐
- 路徑總和 III⭐⭐
- 存在重復(fù)元素 III⭐⭐
- 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)⭐⭐⭐
