天天看點

算法系列之二叉樹理論回顧真題演練

前端仔一隻,不時刷刷算法題防止老年癡呆。本文是個人算法系列中的一篇,如果想了解更多關于算法的内容,請點選部落客的算法專欄檢視。

理論回顧

二叉樹簡介

資料結構中有一種結構是樹,不過一般我們常見的是樹中的一種特殊類型——二叉樹。二叉樹簡單來說就是每個節點最多有兩個子節點。

如果每個節點都有兩個子節點,那麼我們稱這種二叉樹為滿二叉樹。

還有一種二叉樹,其葉子節點都在最底下兩層,最後一層葉子節點都靠左排列,并且除了最後一層,其他層的葉子節點都要達到最大,這種二叉樹叫作完全二叉樹。

算法系列之二叉樹理論回顧真題演練

除了上面那些,這裡還需要特别提到一種樹,二叉搜尋樹。二叉搜尋樹要求,在樹中的任意一個節點,其左子樹中的每個節點的值,都要小于這個節點的值,而右子樹節點的值都大于這個節點的值。

算法系列之二叉樹理論回顧真題演練

二叉樹存儲方式

二叉樹的定義我們已經知道了,但是實際程式設計中我們如何去存儲一個二叉樹呢?主要有兩種方式,鍊式存儲法和順序存儲法。

鍊式存儲法

這種方式簡單,也非常常見,主要通過指針來連接配接不同的節點。

算法系列之二叉樹理論回顧真題演練

順序存儲法

這種存儲方法最适合完全二叉樹,它主要使用數組來進行存儲。

算法系列之二叉樹理論回顧真題演練

二叉樹周遊

主要分為4種周遊方式,

  1. 前序周遊:對于樹中的任意節點來說,先列印這個節點,然後再列印它的左子樹,最後列印它的右子樹。
  2. 中序周遊:對于樹中的任意節點來說,先列印它的左子樹,然後再列印它本身,最後列印它的右子樹。
  3. 後序周遊:對于樹中的任意節點來說,先列印它的左子樹,然後再列印它的右子樹,最後列印這個節點本身。
  4. 按層周遊:從第一層開始,從左到右周遊整棵二叉樹。
注意:前、中、後周遊都針對根節點來說的。如根節點在前,那就是前序。

真題演練

溫習一下概念之後,我們需要做的就是實戰。據部落客多年的經驗,概念的東西隻是簡單的背誦記憶是沒有用的,必須要應用,這樣才能有深刻的了解。話不多說,我們先來一道開胃菜。

二叉樹的最大深度

題目

給定一個二叉樹,找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

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

示例:

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

3
   / \
  9  20
    /  \
   15   7
           

傳回它的最大深度 3 。

解答

這道題是求二叉樹的最大深度,也就是二叉樹的最大層數。做法很簡單從根結點一直加到葉子節點,然後比較所有的個數,求出最大的。

但是怎樣程式設計呢?這裡需要告訴大家一個訣竅,凡是和二叉樹相關的算法題,我們都可以從遞歸的思路分析。因為二叉樹是天然的遞歸結構,是以采用遞歸可以解決很多問題。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) {
        return 0
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};
           

舉一反三:

  • 二叉樹的最小深度

求根到葉子節點數字之和

有了前面的熱身,可能有些人覺得不過瘾。接下來,我們一道中等難度的題。

題目

給定一個二叉樹,它的每個結點都存放一個 0-9 的數字,每條從根到葉子節點的路徑都代表一個數字。

例如,從根到葉子節點路徑 1->2->3 代表數字 123。

計算從根到葉子節點生成的所有數字之和。

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

示例 1:

輸入: [1,2,3]
    1
   / \
  2   3
輸出: 25
解釋:
從根到葉子節點路徑 1->2 代表數字 12.
從根到葉子節點路徑 1->3 代表數字 13.
是以,數字總和 = 12 + 13 = 25.
           

示例 2:

輸入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
輸出: 1026
解釋:
從根到葉子節點路徑 4->9->5 代表數字 495.
從根到葉子節點路徑 4->9->1 代表數字 491.
從根到葉子節點路徑 4->0 代表數字 40.
是以,數字總和 = 495 + 491 + 40 = 1026.
           

解答

這題咋一看有點複雜,不過不要急。仔細閱讀題目後,我們能找出線索。隻要我們把每一條路徑找到,然後把它們的值加起來就行。

問題就轉化成找到每一條路徑。如何去做呢?上一題我們提到了,二叉樹相關的題目可以從遞歸的思路去分析。這裡我們采用遞歸的深度優先周遊(dfs),就可以輕松解決。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    if (root === null) {
        return 0
    } 
    const nums = []
    dfs(root, 0, nums)
    return nums.reduce((total, value, index) => {
        return total + value
    }, 0)
};

const dfs = (root, total, nums) => {
    if (root.left === null && root.right === null) {
        nums.push(total * 10 + root.val)
        return
    }
    if (root.left !== null) {
        dfs(root.left, total * 10 + root.val, nums)
    }
    if (root.right !== null) {
        dfs(root.right, total * 10 + root.val, nums)
    }
}
           

舉一反三:

  • 二叉樹的所有路徑
  • 左葉子之和

翻轉二叉樹

這道題有個故事,有位開源軟體的大佬 Max Howell 去 Google 面試。在白闆上,他沒能寫出這道題,是以被 Google 拒絕了。

題目

翻轉一棵二叉樹。

示例:

輸入:

4
   /   \
  2     7
 / \   / \
1   3 6   9
           

輸出:

4
   /   \
  7     2
 / \   / \
9   6 3   1
           

解答

這道題雖然大佬沒能當場寫出來,但這并不能說明大佬的水準差。這道題就是把左右子樹交換,難點在程式設計實作。如果你沒有思路,不妨還是按照我們前面說的,采用遞歸的思想。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root === null || (root.left === null && root.right == null)) {
        return root
    }
    if (root.left === null) {
        root.left = root.right
        // 特别注意這一步
        root.right = null
    } else if (root.right === null) {
        root.right = root.left
        // 特别注意這一步
        root.left = null
    } else {
        const tree = root.left
        root.left = root.right
        root.right = tree
    }
    invertTree(root.left)
    invertTree(root.right)

    return root
};
           

舉一反三:

  • 相同的樹
  • 對稱二叉樹

如果我的文章可以幫助到大家,請不吝賜贊。另外,如果想及時收到更多關于算法和前端方面的訊息,可以關注我的部落格。

繼續閱讀