算法系列之二叉樹

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

理論回顧

二叉樹簡介

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

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

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

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

二叉樹存儲方式

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

鍊式存儲法

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

順序存儲法

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

二叉樹周遊

主要分為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
};
           

舉一反三：

• 相同的樹
• 對稱二叉樹

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