【算法總結】五道常見的算法-二叉樹

2021-02-21 程式設計師徐公
前言

前段時間，寫了面試必備的一系列文章，反應還不錯。有一些讀者反饋說，能不能整理一些面試常見的算法。前段時間，我恰好總結了 LeetCode 常見的面試算法題目。

https://github.com/gdutxiaoxu/Android_interview

剛開始準備刷算法題目的時候，感覺真的是好難，十道題目有九道是不會的。心中曾一萬隻草泥馬跑過，自己怎麼這麼辣雞。

慢慢得，我發現算法也是一個可以通過練習慢慢成長的。

首先我們要掌握基本的數據結構，數組，鍊表，哈希表， Set，二叉樹，堆，棧等。你要知道他們有什麼優缺點，適應場景是什麼，時間複雜度和空間複雜度是多少。而不能知道簡單的 API。

接著，掌握了這些基本的數據結構之後，一些基本的算法你也要掌握以下，比如快速排序，歸併排序，對排序，二分查找。這些基本的一定要掌握，面試當中經常也會問到。

分類刷題，我們在力扣上面可以看到，https://leetcode-cn.com/problemset/algorithms/ ，刷題是可以按標籤來的。比如鍊表，數組，二分查找，二叉樹，動態規劃等

學好算法不是一日之功，需要長期的積累。建議的做法是每天做一兩道題，題目不在多，貴在於理解。堅持一兩個月，你會發現你的感覺逐漸好起來了

廢話不多說了，開始進入今天的正文。

二叉樹的概念

俗話說得好，萬丈高樓平地起。講解算法之前，我們先來了解一下一些基本的概念。

二叉樹（Binary Tree）是包含n個節點的有限集合，該集合或者為空集（此時，二叉樹稱為空樹），或者由一個根節點和兩棵互不相交的、分別稱為根節點的左子樹和右子樹的二叉樹組成。

一棵典型的二叉樹如下圖所示：

由上述的定義可以看出，二叉樹中的節點至多包含兩棵子樹，分別稱為左子樹和右子樹，而左子樹和右子樹又分別至多包含兩棵子樹。由上述的定義，二叉樹的定義是一種遞歸的定義。
二叉樹種類

滿二叉樹

對於一棵二叉樹，如果每一個非葉子節點都存在左右子樹，並且二叉樹中所有的葉子節點都在同一層中，這樣的二叉樹稱為滿二叉樹。

完全二叉樹

對於一棵具有n個節點的二叉樹按照層次編號，同時，左右子樹按照先左後右編號，如果編號為i的節點與同樣深度的滿二叉樹中編號為i的節點在二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹。

二叉排序樹：

又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

二分查找的時間複雜度是O(log(n))，最壞情況下的時間複雜度是O(n)（相當於順序查找）

平衡二叉樹：

又稱 AVL 樹。平衡二叉樹是二叉搜索樹的進化版，所謂平衡二叉樹指的是，左右兩個子樹的高度差的絕對值不超過 1。

紅黑樹：

紅黑樹是每個節點都帶顏色的樹，節點顏色或是紅色或是黑色，紅黑樹是一種查找樹。紅黑樹有一個重要的性質，從根節點到葉子節點的最長的路徑不多於最短的路徑的長度的兩倍。對於紅黑樹，插入，刪除，查找的複雜度都是O（log N）。

哈夫曼樹：

給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman tree)。

遍歷方式

二叉樹主要有四種遍歷方式

前提：這裡先給出測試中的二叉樹結構，如下圖所示

該二叉樹對應的幾種遍歷方式的結果順序：

先序遍歷：10->6->4->8->14->12->16

中序遍歷：4->6->8->10->12->14->16

後序遍歷：4->8->6->12->16->14->10

層次遍歷：10->6->14->4->8->12->16

遞歸

遞歸的基本思想就是把規模大的問題轉化為規模小的相似的子問題來解決。
特別地，在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況，這也正是遞歸的定義所在。格外重要的是，這個解決問題的函數必須有明確的結束條件，否則就會導致無限遞歸的情況

而在樹當中，一棵樹要麼是空樹，要麼有兩個指針，每個指針指向一棵樹。樹是一種遞歸結構，很多樹的問題可以使用遞歸來處理。

1. 樹的高度1.0 求二叉樹的最大層數(最大深度)

104. Maximum Depth of Binary Tree (Easy)

Leetcode / 力扣

這道題目的解法其實很簡單

1public int maxDepth(TreeNode root) {
2    if (root == null) return 0;
3    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
4}

1.1 二叉樹的最小深度

LeetCode：Minimum Depth of Binary Tree

給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

解題思路


1class Solution {
2    public int minDepth(TreeNode root) {
3        if(root == null)
4            return 0;
5        int left = minDepth(root.left);
6        int right = minDepth(root.right);
7        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
8    }
9}

2. 平衡樹

110. Balanced Binary Tree (Easy)

1    3
2   / \
3  9  20
4    /  \
5   15   7

思路

平衡樹左右子樹高度差都小於等於 1

1private boolean result = true;
2
3public boolean isBalanced(TreeNode root) {
4    maxDepth(root);
5    return result;
6}
7
8public int maxDepth(TreeNode root) {
9    if (root == null) return 0;
10    int l = maxDepth(root.left);
11    int r = maxDepth(root.right);
12    if (Math.abs(l - r) > 1) result = false;
13    return 1 + Math.max(l, r);
14}

3. 兩節點的最長路徑

543. Diameter of Binary Tree (Easy)

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。


解題思路：

因為最長直徑不一定過根節點，所以需要分別以每一個節點為中心計算最長路徑。

用一個全局變量max來維護最長路徑（左子樹的深度+右子樹的深度）。

為了計算每個子樹的深度，使用深度優先遍歷計算樹中每一個節點的深度（max（左子樹深度，右子樹深度））

1Input:
2
3         1
4        / \
5       2  3
6      / \
7     4   5
8
9Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

1private int max = 0;
2
3public int diameterOfBinaryTree(TreeNode root) {
4    depth(root);
5    return max;
6}
7
8private int depth(TreeNode root) {
9    if (root == null) return 0;
10    int leftDepth = depth(root.left);
11    int rightDepth = depth(root.right);
12    max = Math.max(max, leftDepth + rightDepth);
13    return Math.max(leftDepth, rightDepth) + 1;
14}

4. 翻轉樹

226. Invert Binary Tree (Easy)

翻轉一棵二叉樹

思路與算法

這是一道很經典的二叉樹問題。顯然，我們從根節點開始，遞歸地對樹進行遍歷，並從葉子結點先開始翻轉。

如果當前遍歷到的節點 root 的左右兩棵子樹都已經翻轉，那麼我們只需要交換兩棵子樹的位置，即可完成以 root 為根節點的整棵子樹的翻轉。

1public TreeNode invertTree(TreeNode root) {
2    if (root == null) return null;
3    TreeNode left = root.left;  // 後面的操作會改變 left 指針，因此先保存下來
4    root.left = invertTree(root.right);
5    root.right = invertTree(left);
6    return root;
7}

5. 歸併兩棵樹

617. Merge Two Binary Trees (Easy)

Leetcode / 力扣

給定兩個二叉樹，想像當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。

你需要將他們合併為一個新的二叉樹。合併的規則是如果兩個節點重疊，那麼將他們的值相加作為節點合併後的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點。

解題思路

1Input:
2       Tree 1                     Tree 2
3          1                         2
4         / \                       / \
5        3   2                     1   3
6       /                           \   \
7      5                             4   7
8
9Output:
10         3
11        / \
12       4   5
13      / \   \
14     5   4   7

1public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
2    if (t1 == null && t2 == null) return null;
3    if (t1 == null) return t2;
4    if (t2 == null) return t1;
5    TreeNode root = new TreeNode(t1.val + t2.val);
6    root.left = mergeTrees(t1.left, t2.left);
7    root.right = mergeTrees(t1.right, t2.right);
8    return root;
9}

這篇文章主要講解了二叉樹的一些基本概念，以及一些常見的遞歸算法題目，看起來挺簡單的，但是讓你寫，你寫得出來嘛？算法這種東西，要多練，動手實踐，印象才深刻。所有的算法題目以及面試相關的，我都放在這個目錄下，有空可以幫我 start 一下，謝謝。https://github.com/gdutxiaoxu/Android_interview

相關焦點

  • 二叉樹算法,你懂嗎?
    聊聊面試點：一、樹 & 二叉樹樹的組成為節點和邊，節點用來儲存元素。節點組成為根節點、父節點和子節點。如圖：樹深 length 為 4；根節點的值為 5 ；父子節點關係：值為 8 和 值為 3 的節點
  • 二叉樹算法大盤點
    ，基本只要接觸算法這一類的都一定會碰到的，所以我打算通過一篇文章，對二叉樹結構的相關算法進行總結匯總，思路和代碼實現相結合，讓你不在懼怕二叉樹。（ps：後面我還想寫一篇樹結構的高級篇，就是多叉數，就是對我平時看算法論文碰到的一些新奇的算法，比如B樹、B+樹，還有我一種叫做Bed樹的新奇算法等等）下面的思路講解中，我會給出一個類偽代碼的思路，然後進行相關說明，也就是一種思路框架，有了思路框架，以後碰到問題就直接交給框架完成。
  • 二叉樹算法大盤點 | 原力計劃
    樹結構對於程式設計師來說應該不陌生，特別是二叉樹，基本只要接觸算法這一類的都一定會碰到的，所以我打算通過一篇文章，對二叉樹結構的相關算法進行總結匯總
  • 數據結構和算法學習指南
    首先，這裡講的都是普通的數據結構和算法，咱不是搞競賽的，野路子出生，只解決常規的問題，以面試為最終目標。另外，以下是我個人的經驗的總結，沒有哪本算法書會寫這些東西，所以請讀者試著理解我的角度，別糾結於細節問題，因為這篇文章就是對數據結構和算法建立一個框架性的認識。
  • 數據結構與算法大總結
    數據結構知識綜述一、前言經過一個學期對數據結構與算法的學習，對這門課程有了更深入的了解，了解到了數據結構的相關知識，明白了，數據結構的重要性及應用，回顧一個學期，通過這個小論文，來總結一學期的學習成果，數據結構這門課程，具有一定的深度和廣度，有其複雜性，我們一起來分析一下
  • 微信大佬總結的算法學習經驗
    你會發現這種做法效率很低，那道題目就算被做出來了，也不代表就可以解出其它的題目。合理的做法是循序漸進。如果你本身有基礎，熟練度高，那你刷簡單的leetcode應該是幾分鐘一題，幾分鐘一題的，花不了你多少時間。如果你刷簡單都花費很長時間，說明熟練度不夠，就更應該從簡單開始。然後過度到中等，再過度到困難。
  • 手寫二叉樹?程式設計師面試最常見問題TOP 48
    近來正值秋招季節，很多編程面試都要求手寫數據結構手推機器學習算法。各位同學為了面試也會刷各種編程題，其中數據結構與排序搜索算法又是最為基礎的內容。在本文中，我們為各位讀者準備了 48 道基礎面試題，它可以幫助我們更深地理解數據結構。本文所有面試題都提供了 Java 解決方案，並介紹了比較流行的 GitHub 面試題項目。
  • 程式設計師必會算法系列之——「遞歸算法」
    講遞歸算法時會涉及到「棧」數據結構的一些知識，如果有不太了解的可以看這裡遞歸的缺點使用遞歸算法時每次方法的調用都需要在棧中開闢出一個空間保存相關數據，頻繁的壓棧、彈棧會導致效率變低。遞歸使用注意事項1、使用遞歸算法解決問題必須要有出口，不然就形成死循環了。
  • 快速入門數據結構和算法
    阿里妹導讀：有哪些常見的數據結構？基本操作是什麼？常見的排序算法是如何實現的？各有什麼優缺點？
  • 【原創教程】數據結構與算法(1)——二叉樹
    一、二叉樹二叉樹是一種更為典型的樹樹狀結構。
  • 二叉樹的常用算法
    節點訪問的次序,忽略列印行為如果將列印安排在同個數字第一次被訪問時,第一次即先序遍歷第二次即中序遍歷第三次即後序遍歷現二叉樹的先序、中序、後序遍歷，包括遞歸方式和非遞歸方式二叉樹結構定義public static class Node {        public
  • 「算法與數據結構」二叉樹之美
    從圖中來看，以上的五個特點都可以很好的總結出來除根節點（A）外，其他的節點都有父節點，並且每個節點只有有限個子節點或無子節點。二叉樹的遍歷我們知道對於二叉樹的遍歷而言，有常見得三種遍歷方式，分別是以下三種：對於任何一種遍歷方式而言，我們不僅需要掌握它的非遞歸版本，同時對於它的遞歸版本來說，更是考察一個人的算法基本功，那麼接下來，我們來看看吧。
  • 五.決策樹算法(上)
    所以可以使用信息增益來進行決策樹的劃分屬性選擇，比如ID3算法。(5).缺點         ID3算法傾向於選擇取值較多的屬性，有些情況下這些屬性可能沒有價值。        ID3算法只能對離散型屬性的數據集構造決策樹。
  • Python 算法基礎班 | 從零開始學Python!
    ：使用 Python學習常見的算法和數據結構，並且解決常見的 Python 算法面試問題。Python基礎入門變量及其運算Reverse 3-digit IntegerSwap Two Variables登陸http://t.cn/RAC7Era，註冊帳號並報名《九章算法基礎班（Python）》上過《九章算法班》、《九章算法強化班》、《系統設計班》，
  • 力扣(LeetCode)- 常見的排序算法總結
    如何分析一個排序算法好壞時間複雜度、比較和交換次數、原地排序（空間複雜度為(1)）、排序穩定性（相等元素之間的位置先後順序不變）。有序度：是數組中具有有序關係的元素對的個數逆序度：和有序度相反。選擇排序是不穩定排序，所以應用最少。
  • TOP 48 算法和編程面試題,牛逼啊!
    我們在面試中經常看到的領域是數組、鍊表、字符串、二叉樹以及有關算法的問題（例如字符串算法、快速排序或基數排序等排序算法），本文將介紹這些內容。雖然本文無法覆蓋你在面試中將要面臨的所有問題，但是它可以給你提供足夠的思路，讓你在面試時對於各種挑戰有所準備。一旦解決了這些問題，你就可以有信心面對任何電話面試或現場面試了。
  • 結構與算法:二叉樹與多叉樹
    二、二叉樹模型樹的種類有很多，二叉樹（BinaryTree）是樹形結構的一個重要類型，每個節點最多只能有兩個子節點的一種形式稱為二叉樹，二叉樹的子節點分為左節點和右節點，許多實際問題抽象出來的數據結構往往是二叉樹形式。
  • BFS 算法框架套路詳解
    本文就由淺入深寫兩道 BFS 的典型題目，分別是「二叉樹的最小高度」和「打開密碼鎖的最少步數」，手把手教你怎麼寫 BFS 算法。一、算法框架要說框架的話，我們先舉例一下 BFS 出現的常見場景好吧，問題的本質就是讓你在一幅「圖」中找到從起點start到終點target的最近距離，這個例子聽起來很枯燥，但是 BFS 算法問題其實都是在幹這個事兒。
  • 算法筆記-1:算法、離散數學碎碎念
    與看第一章「排序算法」的時候的驚為天人不同。這逼得我不得不求助於號稱看懂就能秒殺90%程序猿的《算法導論》（《算法導論》Thomas H Cormen等著，潘金貴 等譯，機械工業出版社）看了一陣後我得出結論：我屬於那被秒殺的90%
  • 如何從菜雞變成收割機,大廠面試的算法,你懂了嗎?
    讓大廠面試顯得逼格很高，是算法和數據結構嗎？是的！！！Google工程師曾總結過，大廠之所以愛考察算法和數據結構是因為：算法能力能夠準確辨別一個程式設計師的技術功底是否紮實；算法能力是發掘程式設計師的學習能力與成長潛力的關鍵手段；算法能力能夠協助判斷程式設計師在面對新問題時，分析並解決問題的能力；算法能力是設計一個高性能系統、性能優化的必備基礎。