|
今天是小浩算法 “365刷題計(jì)劃” 二叉樹入門 - 整合篇,。本篇作為入門整合篇，已經(jīng)砍去難度較大的知識(shí)點(diǎn),，所有列出的內(nèi)容,，均為必須掌握。因?yàn)楹荛L,，寫下目錄：
01 PART 二叉樹是啥 二叉樹有多重要,？單就面試而言，在 leetcode 中二叉樹相關(guān)的題目占據(jù)了300多道,，近三分之一,。同時(shí)，二叉樹在整個(gè)算法板塊中還起到承上啟下的作用：不但是數(shù)組和鏈表的延伸,，又可以作為圖的基礎(chǔ),?？傊浅Ｖ匾?！ 什么是二叉樹,？官方是這樣定義的：在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu),。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）,。 上面那是個(gè)玩笑，二叉樹長這樣： 二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆,。樹比鏈表稍微復(fù)雜,，因?yàn)殒湵硎蔷€性數(shù)據(jù)結(jié)構(gòu)，而樹不是,。樹的問題很多都可以由廣度優(yōu)先搜索或深度優(yōu)先搜索解決,。 一般而言，我們會(huì)看到下面這些與樹相關(guān)的術(shù)語： 小浩概念 與樹相關(guān)的術(shù)語 樹的結(jié)點(diǎn)（node）：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支,； 孩子結(jié)點(diǎn)（child node）：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子； 雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子,，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親,； 兄弟結(jié)點(diǎn)：同一雙親的孩子結(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)都稱為該結(jié)點(diǎn)的子孫 結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1,；根的孩子為第二層結(jié)點(diǎn)，依此類推,； 樹的深度：樹中最大的結(jié)點(diǎn)層 結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù) 樹的度：樹中最大的結(jié)點(diǎn)度,。 葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn),； 分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn),； 有序樹：子樹有序的樹，比如家族樹,； 無序樹：不考慮子樹的順序,； 了解了上面的基本概念之后。我們將通過幾道例題,，為大家引入樹的經(jīng)典操作,。 02 PART 二叉樹最大深度 復(fù)習(xí)上面的概念：樹的深度指的是樹中最大的結(jié)點(diǎn)層。 第104題：給定一個(gè)二叉樹,，找出其最大深度,。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。 說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn),。 示例： 給定二叉樹 [3,9,20,null,null,15,7],， 3/ \9 20/ \15 7 基本概念掌握：每個(gè)節(jié)點(diǎn)的深度與它左右子樹的深度有關(guān),，且等于其左右子樹最大深度值加上 1。即： maxDepth(root) = max(maxDepth(root.left),maxDepth(root.right)) + 1 以 [3,9,20,null,null,15,7] 為例：
maxDepth(root-3) 根據(jù)分析，我們通過遞歸進(jìn)行求解： 1//Go2func maxDepth(root *TreeNode) int {3 if root == nil {4 return 05 }6 return max(maxDepth(root.Left), maxDepth(root.Right)) + 17}89func max(a int, b int) int {10 if a > b {11 return a12 }13 return b14}
其實(shí)我們上面用的遞歸方式,，本質(zhì)上是使用了DFS的思想,。所以這里就可以引出什么是DFS：深度優(yōu)先搜索算法（Depth First Search），對于二叉樹而言,，它沿著樹的深度遍歷樹的節(jié)點(diǎn),，盡可能深的搜索樹的分支，這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止,。( 注意,，這里的前提是對二叉樹而言。DFS本身作為圖算法的一種,，在后續(xù)我會(huì)單獨(dú)拉出來和回溯放一起講,。) 如上圖二叉樹，它的訪問順序?yàn)椋?/p> A-B-D-E-C-F-G 到這里,，我們思考一個(gè)問題,？雖然我們用遞歸的方式根據(jù)DFS的思想順利完成了題目。但是這種方式的缺點(diǎn)卻顯而易見,。因?yàn)?strong>在遞歸中,，如果層級過深，我們很可能保存過多的臨時(shí)變量,，導(dǎo)致棧溢出,。這也是為什么我們一般不在后臺(tái)代碼中使用遞歸的原因。如果不理解,，下面我們詳細(xì)說明： 事實(shí)上,，函數(shù)調(diào)用的參數(shù)是通過棧空間來傳遞的,，在調(diào)用過程中會(huì)占用線程的棧資源,。而遞歸調(diào)用，只有走到最后的結(jié)束點(diǎn)后函數(shù)才能依次退出,，而未到達(dá)最后的結(jié)束點(diǎn)之前,，占用的?？臻g一直沒有釋放，如果遞歸調(diào)用次數(shù)過多,，就可能導(dǎo)致占用的棧資源超過線程的最大值,，從而導(dǎo)致棧溢出，導(dǎo)致程序的異常退出,。 所以,，我們引出下面的話題：如何將遞歸的代碼轉(zhuǎn)化成非遞歸的形式。這里請記住,，基本所有的遞歸轉(zhuǎn)非遞歸,，都可以通過棧來進(jìn)行實(shí)現(xiàn)。非遞歸的DFS,，代碼如下： 1//java2private List<TreeNode> traversal(TreeNode root) {3 List<TreeNode> res = new ArrayList<>();4 Stack<TreeNode> stack = new Stack<>();5 stack.add(root);6 while (!stack.empty()) {7 TreeNode node = stack.peek();8 res.add(node);9 stack.pop();10 if (node.right != null) {11 stack.push(node.right);12 }13 if (node.left != null) {14 stack.push(node.left);15 }16 }17 return res;18}
上面的代碼,，唯一需要強(qiáng)調(diào)的是，為什么需要先右后左壓入數(shù)據(jù),？是因?yàn)槲覀冃枰獙⑾仍L問的數(shù)據(jù),，后壓入棧（請思考棧的特點(diǎn)）。 如果不理解代碼,，請看下圖：
說明：
至此，非遞歸的 DFS 就講解完畢了,。那如何通過非遞歸DFS的方式,，來對本題求解呢？相信已經(jīng)很簡單了,，這個(gè)下去自己試試就ok了了,。 03 PART 二叉樹的層次遍歷
在上文中，我們通過例題學(xué)習(xí)了二叉樹的DFS（深度優(yōu)先搜索）,，其實(shí)就是沿著一個(gè)方向一直向下遍歷,。那我們可不可以按照高度一層一層的訪問樹中的數(shù)據(jù)呢？當(dāng)然可以,，就是本節(jié)中我們要講的BFS（寬度優(yōu)先搜索）,，同時(shí)也被稱為廣度優(yōu)先搜索,。 第102題：給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值,。（即逐層地,，從左到右訪問所有節(jié)點(diǎn)）。 例如: 給定二叉樹: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其層次遍歷結(jié)果：[[3],[9,20],[15,7]] BFS,，廣度/寬度優(yōu)先,。說白了就是從上到下，先把每一層遍歷完之后再遍歷一下一層,。假如我們的樹如下：
按照BFS,，訪問順序如下：
了解了BFS，我們開始對本題進(jìn)行分析,。同樣,，我們先考慮本題的遞歸解法。想到遞歸,，我們一般先想到DFS,。我們可以對該二叉樹進(jìn)行先序遍歷（根左右的順序），同時(shí),，記錄節(jié)點(diǎn)所在的層次level,，并且對每一層都定義一個(gè)數(shù)組，然后將訪問到的節(jié)點(diǎn)值放入對應(yīng)層的數(shù)組中,。 假設(shè)給定二叉樹為[3,9,20,null,null,15,7],，圖解如下：
根據(jù)分析，代碼如下： 1//Go2func levelOrder(root *TreeNode) [][]int {3 return dfs(root, 0, [][]int{})4}56func dfs(root *TreeNode, level int, res [][]int) [][]int {7 if root == nil {8 return res9 }10 if len(res) == level {11 res = append(res, []int{root.Val})12 } else {13 res[level] = append(res[level], root.Val)14 }15 res = dfs(root.Left, level+1, res)16 res = dfs(root.Right, level+1, res)17 return res18}
上面的解法,，其實(shí)相當(dāng)于是用DFS的方法實(shí)現(xiàn)了二叉樹的BFS,。那我們能不能直接使用BFS的方式進(jìn)行解題呢？當(dāng)然可以,。我們使用Queue的數(shù)據(jù)結(jié)構(gòu),。我們將root節(jié)點(diǎn)初始化進(jìn)隊(duì)列，通過消耗尾部,，插入頭部的方式來完成BFS,。 具體步驟如下圖：
根據(jù)分析，完成代碼： 1//Go2func levelOrder(root *TreeNode) [][]int {3 var result [][]int4 if root == nil {5 return result6 }7 // 定義一個(gè)雙向隊(duì)列8 queue := list.New()9 // 頭部插入根節(jié)點(diǎn)10 queue.PushFront(root)11 // 進(jìn)行廣度搜索12 for queue.Len() > 0 {13 var currentLevel []int14 listLength := queue.Len()15 for i := 0; i < listLength; i++ {16 // queue.Back()：返回隊(duì)列中最后一個(gè)元素17 // queue.Remove(queue.Back()).(*TreeNode) ： 移除隊(duì)列中最后一個(gè)元素并將其轉(zhuǎn)化為TreeNode類型18 node := queue.Remove(queue.Back()).(*TreeNode)19 currentLevel = append(currentLevel, node.Val)20 if node.Left != nil {21 queue.PushFront(node.Left)22 }23 if node.Right != nil {24 queue.PushFront(node.Right)25 }26 }27 result = append(result, currentLevel)28 }29 return result30}
04 PART 二叉搜索樹
BST是二叉搜索樹,，很重要,。BST是二叉搜索樹，很重要,。BST是二叉搜索樹,，很重要。重要的事情說三遍。 第98題：給定一個(gè)二叉樹,，判斷其是否是一個(gè)有效的二叉搜索樹,。 示例 1: 輸入: 5 / \ 1 4 / \ 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]。 根節(jié)點(diǎn)的值為 5 ,，但是其右子節(jié)點(diǎn)值為 4 ,。 要驗(yàn)證二叉搜索樹，首先得知道啥是二叉搜索樹,。二叉搜索樹（Binary Search Tree）,，（又：二叉查找樹，二叉排序樹）它或者是一棵空樹,，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空,，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹不空,，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值,；它的左、右子樹也分別為二叉搜索樹,。 這里強(qiáng)調(diào)一下子樹的概念：設(shè)T是有根樹,，a是T中的一個(gè)頂點(diǎn)，由a以及a的所有后裔（后代）導(dǎo)出的子圖稱為有向樹T的子樹,。具體來說,，子樹就是樹的其中一個(gè)節(jié)點(diǎn)以及其下面的所有的節(jié)點(diǎn)所構(gòu)成的樹。比如下面這就是一顆二叉搜索樹：
下面這兩個(gè)都不是：
回到題目,，那我們?nèi)绾蝸眚?yàn)證一顆二叉搜索樹,？首先看完題目,，我們很容易想到 遍歷整棵樹,，比較所有節(jié)點(diǎn),，通過 左節(jié)點(diǎn)值<節(jié)點(diǎn)值，右節(jié)點(diǎn)值＞節(jié)點(diǎn)值 的方式來進(jìn)行求解,。但是這種解法是錯(cuò)誤的,，因?yàn)?strong>對于任意一個(gè)節(jié)點(diǎn),，我們不光需要左節(jié)點(diǎn)值小于該節(jié)點(diǎn),，并且左子樹上的所有節(jié)點(diǎn)值都需要小于該節(jié)點(diǎn)。（右節(jié)點(diǎn)一致）所以我們在此引入上界與下界,，用以保存之前的節(jié)點(diǎn)中出現(xiàn)的最大值與最小值,。 代碼其實(shí)很簡單： 1//GO2func isValidBST(root *TreeNode) bool {3 if root == nil{4 return true5 }6 return isBST(root,math.MinInt64,math.MaxInt64)7}89func isBST(root *TreeNode,min, max int) bool{10 if root == nil{11 return true12 }13 if min >= root.Val || max <= root.Val{14 return false15 }16 return isBST(root.Left,min,root.Val) && isBST(root.Right,root.Val,max)17}
難就難在，可能大家看不懂這個(gè)遞歸,！沒事,，祭出大殺器：
這里需要強(qiáng)調(diào)的是，在每次遞歸中，我們除了進(jìn)行左右節(jié)點(diǎn)的校驗(yàn),，還需要與上下界進(jìn)行判斷,。其余的就很簡單了。 05 PART BST的查找
在上文中,，我們學(xué)習(xí)了二叉搜索樹,。那我們?nèi)绾卧诙嫠阉鳂渲胁檎乙粋€(gè)元素呢？ 第700題：給定二叉搜索樹（BST）的根節(jié)點(diǎn)和一個(gè)值,。你需要在BST中找到節(jié)點(diǎn)值等于給定值的節(jié)點(diǎn),。返回以該節(jié)點(diǎn)為根的子樹。如果節(jié)點(diǎn)不存在,，則返回 NULL,。 例如，給定二叉搜索樹: 4 / \ 2 7 / \ 1 3 搜索: 2 你應(yīng)該返回如下子樹: 2 / \ 1 3 在上述示例中,，如果要找的值是 5,，但因?yàn)闆]有節(jié)點(diǎn)值為 5，我們應(yīng)該返回 NULL,。 先復(fù)習(xí)一下,，二叉搜索樹（BST）的特性： 1.若它的左子樹不為空，則所有左子樹上的值均小于其根節(jié)點(diǎn)的值 2.若它的右子樹不為空,，則所有右子樹上的值均大于其根節(jié)點(diǎn)得值 3.它的左右子樹也分別為二叉搜索樹 如下圖就是一棵典型的BST：
現(xiàn)在我們來看題,，假設(shè)目標(biāo)值為 val。根據(jù)BST的特性,，我們可以很容易想到查找過程（上面的驗(yàn)證比查找稍難一點(diǎn)）：
很簡單,，不是嗎？然后我們可以給出迭代和遞歸兩種解法（給個(gè)Java的吧?。?/p> 1//java23//遞歸4public TreeNode searchBST(TreeNode root, int val) {5 if (root == null)6 return null;7 if (root.val > val) {8 return searchBST(root.left, val);9 } else if (root.val < val) {10 return searchBST(root.right, val);11 } else {12 return root;13 }14}1516//迭代17public TreeNode searchBST(TreeNode root, int val) {18 while (root != null) {19 if (root.val == val) {20 return root;21 } else if (root.val > val) {22 root = root.left;23 } else {24 root = root.right;25 }26 }27 return null;28}
06 PART BST的刪除
查找有了,，下面自然就要講刪除。（為啥說我要著重墨在BST上面,，因?yàn)锽ST這兩年在面試時(shí)非常高頻,。面試官不可能說問你一個(gè)普通二叉樹的題目，要么就是問堆,，要么就是問BST,，或者就直接DFS考察回溯。） 第450題：給定一個(gè)二叉搜索樹的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點(diǎn),，并保證二叉搜索樹的性質(zhì)不變,。返回二叉搜索樹（有可能被更新）的根節(jié)點(diǎn)的引用。 一般來說,，刪除節(jié)點(diǎn)可分為兩個(gè)步驟： 首先找到需要?jiǎng)h除的節(jié)點(diǎn),； 如果找到了，刪除它,。 說明：要求算法時(shí)間復(fù)雜度為 O(h),，h 為樹的高度。 示例: root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 給定需要?jiǎng)h除的節(jié)點(diǎn)值是 3,，所以我們首先找到 3 這個(gè)節(jié)點(diǎn),，然后刪除它。 一個(gè)正確的答案是 [5,4,6,2,null,null,7], 如下圖所示,。 5 / \ 4 6 / \ 2 7 另一個(gè)正確答案是 [5,2,6,null,4,null,7],。 5 / \ 2 6 \ \ 4 7 如果你看到了這里，相信肯定知道BST是個(gè)啥了,。所以直接分析題目,。我們要?jiǎng)h除BST的一個(gè)節(jié)點(diǎn)，首先需要找到該節(jié)點(diǎn),。而找到之后,，會(huì)出現(xiàn)三種情況。
分析完畢，直接上代碼,。這里我們給出通過后繼節(jié)點(diǎn)來替代自己的方案（可以自行實(shí)現(xiàn)另一種方案）： 1//go2func deleteNode(root *TreeNode, key int) *TreeNode {3 if root == nil {4 return nil5 }6 if key < root.Val {7 root.Left = deleteNode( root.Left, key )8 return root9 }10 if key > root.Val {11 root.Right = deleteNode( root.Right, key )12 return root13 }14 //到這里意味已經(jīng)查找到目標(biāo)15 if root.Right == nil {16 //右子樹為空17 return root.Left18 }19 if root.Left == nil {20 //左子樹為空21 return root.Right22 }23 minNode := root.Right24 for minNode.Left != nil {25 //查找后繼26 minNode = minNode.Left27 }28 root.Val = minNode.Val29 root.Right = deleteMinNode( root.Right )30 return root31}323334func deleteMinNode( root *TreeNode ) *TreeNode {35 if root.Left == nil {36 pRight := root.Right37 root.Right = nil38 return pRight39 }40 root.Left = deleteMinNode( root.Left )41 return root42}
07 PART 平衡二叉樹
BST講解完了,。上面也說了，別人考察我們肯定是考察特殊的,。那二叉樹里還有啥特殊的東東嘞,？平衡二叉樹算是一個(gè),。 第110題：給定一個(gè)二叉樹,，判斷它是否是高度平衡的二叉樹。 本題中，一棵高度平衡二叉樹定義為： 一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過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 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 題其實(shí)是一道很簡單的題,，主要是拿來復(fù)習(xí)一下高度,。我們想判斷一棵樹是否滿足平衡二叉樹，無非就是判斷當(dāng)前結(jié)點(diǎn)的兩個(gè)孩子是否滿足平衡,，同時(shí)兩個(gè)孩子的高度差是否超過1,。那只要我們可以得到高度，再基于高度進(jìn)行判斷即可,。
這里唯一要注意的是,，當(dāng)我們判定其中任意一個(gè)節(jié)點(diǎn)如果不滿足平衡二叉樹時(shí)，那說明整棵樹已經(jīng)不是一顆平衡二叉樹,，我們可以對其進(jìn)行阻斷,，不需要繼續(xù)遞歸下去。 然后還有一個(gè)初學(xué)者容易懵逼的：
這玩意,，并不是平衡二叉樹,。上代碼： 1//GO2func isBalanced(root *TreeNode) bool {3 if root == nil {4 return true5 }6 l := maxDepth(root.Left)7 r := maxDepth(root.Right)8 if abs(l-r)>1 {9 return false10 }11 if isBalanced(root.Left){12 return true13 }14 return isBalanced(root.Right)15}1617func maxDepth(root *TreeNode) int {18 if root == nil {19 return 020 }21 return max(maxDepth(root.Left),maxDepth(root.Right)) + 122}2324func max(a,b int) int {25 if a > b {26 return a27 }28 return b29}3031func abs(a int) int {32 if a < 0 {33 return -a34 }35 return a 36}
08 PART 完全二叉樹
還有啥特殊的，要撈出來講一講的,？ 第222題：給出一個(gè)完全二叉樹,，求出該樹的節(jié)點(diǎn)個(gè)數(shù)。 說明： 完全二叉樹的定義如下：在完全二叉樹中,，除了最底層節(jié)點(diǎn)可能沒填滿外,，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置,。若最底層為第 h 層,，則該層包含 1~ 2h 個(gè)節(jié)點(diǎn)。 示例: 輸入: 1 / \ 2 3 / \ / 4 5 6 輸出: 6 老樣子,，我們得說說啥是完全二叉樹,。完全二叉樹由滿二叉樹引出，先來了解一下什么是滿二叉樹,。如果二叉樹中除了葉子結(jié)點(diǎn),，每個(gè)結(jié)點(diǎn)的度都為 2，則此二叉樹稱為滿二叉樹,。（二叉樹的度代表某個(gè)結(jié)點(diǎn)的孩子或者說直接后繼的個(gè)數(shù),，這個(gè)在上面已經(jīng)說過了。對于二叉樹而言,，1度是只有一個(gè)孩子或者說單子樹,，2度是有兩個(gè)孩子或者說左右子樹都有,。）
那什么又是完全二叉樹呢：如果二叉樹中除去最后一層節(jié)點(diǎn)為滿二叉樹，且最后一層的結(jié)點(diǎn)依次從左到右分布,，則此二叉樹被稱為完全二叉樹,。比如下面這顆：
這個(gè)就不是：
上面做了這么多題了，你應(yīng)該能想到我要說啥 --- 遞歸,。二叉樹的題目基本上都可以遞歸求解,。 1func countNodes(root *TreeNode) int {2 if root != nil {3 return 045 }6 return 1 + countNodes(root.Right) + countNodes(root.Left)7}
但是很明顯，出題者肯定不是要這種答案,。因?yàn)?strong>這種答案和完全二叉樹一毛錢關(guān)系都沒有,。所以我們繼續(xù)思考。 由于題中已經(jīng)告訴我們這是一顆完全二叉樹,，我們又已知了完全二叉樹除了最后一層,，其他層都是滿的，并且最后一層的節(jié)點(diǎn)全部靠向了左邊,。那我們可以想到,，可以將該完全二叉樹可以分割成若干滿二叉樹和完全二叉樹，滿二叉樹直接根據(jù)層高h(yuǎn)計(jì)算出節(jié)點(diǎn)為2^h-1,，然后繼續(xù)計(jì)算子樹中完全二叉樹節(jié)點(diǎn),。那如何分割成若干滿二叉樹和完全二叉樹呢？對任意一個(gè)子樹,，遍歷其左子樹層高left,，右子樹層高right，相等左子樹則是滿二叉樹,，否則右子樹是滿二叉樹,。這里可能不容易理解，我們看圖,。 假如我們有樹如下：
我們看到根節(jié)點(diǎn)的左右子樹高度都為3,，那么說明左子樹是一顆滿二叉樹。因?yàn)楣?jié)點(diǎn)已經(jīng)填充到右子樹了,，左子樹必定已經(jīng)填滿了,。所以左子樹的節(jié)點(diǎn)總數(shù)我們可以直接得到，是2^left - 1,，加上當(dāng)前這個(gè)root節(jié)點(diǎn),，則正好是2^3，即 8,。然后只需要再對右子樹進(jìn)行遞歸統(tǒng)計(jì)即可,。
那假如我們的樹是這樣：
我們看到左子樹高度為3，右子樹高度為2,。說明此時(shí)最后一層不滿,，但倒數(shù)第二層已經(jīng)滿了,，可以直接得到右子樹的節(jié)點(diǎn)個(gè)數(shù)。同理,，右子樹節(jié)點(diǎn)+root節(jié)點(diǎn),，總數(shù)為2^right,，即2^2,。再對左子樹進(jìn)行遞歸查找。
根據(jù)分析,，得出代碼： 1//java2class Solution {3 public int countNodes(TreeNode root) {4 if (root == null) {5 return 0;6 }7 int left = countLevel(root.left);8 int right = countLevel(root.right);9 if (left == right) {10 return countNodes(root.right) + (1 << left);11 } else {12 return countNodes(root.left) + (1 << right);13 }14 }1516 private int countLevel(TreeNode root) {17 int level = 0;18 while (root != null) {19 level++;20 root = root.left;21 }22 return level;23 }24}
09 PART 二叉樹的剪枝
該講的都講了,，突然想到忘了一個(gè)經(jīng)典操作 - 剪枝。迅速補(bǔ)上,！非常重要,！這里額外說一點(diǎn)，就本人而言,，對這個(gè)操作以及其衍化形式的使用會(huì)比較頻繁,。因?yàn)槲沂亲龇雌墼p的，機(jī)器學(xué)習(xí)里有一個(gè)概念叫做決策樹,，那如果一顆決策樹完全生長,，就會(huì)帶來比較大的過擬合問題。因?yàn)橥耆L的決策樹,，每個(gè)節(jié)點(diǎn)只會(huì)包含一個(gè)樣本,。所以我們就需要對決策樹進(jìn)行剪枝操作，來提升整個(gè)決策模型的泛化能力... 聽不懂也沒關(guān)系,，簡單點(diǎn)講,，就是我覺得這個(gè)很重要，或者每道算法題都很重要,。如果你在工作中沒有用到,，不是說明算法不重要，而可能是你還不夠重要,。 第814題：給定二叉樹根結(jié)點(diǎn) root ,，此外樹的每個(gè)結(jié)點(diǎn)的值要么是 0，要么是 1,。返回移除了所有不包含 1 的子樹的原二叉樹,。 ( 節(jié)點(diǎn) X 的子樹為 X 本身，以及所有 X 的后代,。) 示例1: 輸入: [1,null,0,0,1] 輸出: [1,null,0,null,1] 解釋: 只有紅色節(jié)點(diǎn)滿足條件“所有不包含 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 個(gè)節(jié)點(diǎn),。 每個(gè)節(jié)點(diǎn)的值只會(huì)為 0 或 1 ,。 還是先解釋一下,，啥是剪枝：假設(shè)有一棵樹，最上層的是root節(jié)點(diǎn),，而父節(jié)點(diǎn)會(huì)依賴子節(jié)點(diǎn),。如果現(xiàn)在有一些節(jié)點(diǎn)已經(jīng)標(biāo)記為無效，我們要?jiǎng)h除這些無效節(jié)點(diǎn),。如果無效節(jié)點(diǎn)的依賴的節(jié)點(diǎn)還有效,，那么不應(yīng)該刪除，如果無效節(jié)點(diǎn)和它的子節(jié)點(diǎn)都無效,，則可以刪除,。剪掉這些節(jié)點(diǎn)的過程，稱為剪枝,，目的是用來處理二叉樹模型中的依賴問題,。 說了好多遍了，二叉樹的問題,，大多都可以通過遞歸進(jìn)行求解,。直接分析。假設(shè)我們有二叉樹如下：[0,1,0,1,0,0,0,0,1,1,0,1,0]： 長這樣：
剪枝之后是這樣：
剪什么大家應(yīng)該都能理解,。那關(guān)鍵是怎么剪,？過程也很簡單，在遞歸的過程中,，如果當(dāng)前結(jié)點(diǎn)的左右節(jié)點(diǎn)皆為空,，且當(dāng)前結(jié)點(diǎn)為0，我們就將當(dāng)前節(jié)點(diǎn)剪掉即可,。
其實(shí)很簡單,，直接看代碼： 1func pruneTree(root *TreeNode) *TreeNode {2 return deal(root)3}45func deal(node *TreeNode) *TreeNode {6 if node == nil {7 return nil8 }9 node.Left = deal(node.Left)10 node.Right = deal(node.Right)11 if node.Left == nil && node.Right == nil && node.Val == 0 {12 return nil13 }14 return node15}
10 PART |
|
|
