【Leetcode 做題學演算法周刊】第五期

来源:https://www.cnblogs.com/McChen/archive/2019/12/06/11998902.html
-Advertisement-
Play Games

首發於微信公眾號《前端成長記》，寫於 2019.12.06 背景 本文記錄刷題過程中的整個思考過程，以供參考。主要內容涵蓋： 題目分析設想 編寫代碼驗證 查閱他人解法 思考總結 目錄 "100.相同的樹" "101.對稱二叉樹" "104.二叉樹的最大深度" "107.二叉樹的層次遍歷II" "10 ...


首發於微信公眾號《前端成長記》，寫於 2019.12.06

背景

本文記錄刷題過程中的整個思考過程，以供參考。主要內容涵蓋：

  • 題目分析設想
  • 編寫代碼驗證
  • 查閱他人解法
  • 思考總結

目錄

Easy

100.相同的樹

題目地址

題目描述

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。

如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。

示例：

輸入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

輸入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

輸出: false

輸入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

題目分析設想

題目直接說了是二叉樹，而二叉樹的遍歷方式有兩種：深度優先和廣度優先，我就從這兩個思路來作答。

編寫代碼驗證

Ⅰ.深度優先

代碼：

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    if (p.val !== q.val) return false

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

結果：

  • 57/57 cases passed (52 ms)
  • Your runtime beats 98.81 % of javascript submissions
  • Your memory usage beats 16.66 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n) ，n 為節點個數

Ⅱ.廣度優先

代碼：

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    let pQ =[p] // 左側比較隊列
    let qQ =[q] // 右側比較隊列

    let res = true

    while(true) {
        if (!pQ.length || !qQ.length) {
            res = pQ.length === qQ.length
            break
        }
        // 當前比較節點
        let curP = pQ.shift()
        let curQ = qQ.shift()
        if ((curP && !curQ) || (!curP && curQ) || (curP && curQ && curP.val !== curQ.val)) {
            res = false
            break
        } else {
            let pL = curP ? curP.left : null
            let pR = curP ? curP.right : null
            if (pL || pR) { // 至少一個存在才有意義
                pQ.push(pL, pR) // 依次推入比較數組，實際上就是廣度優先
            }
            let qL = curQ ? curQ.left : null
            let qR = curQ ? curQ.right : null
            if (qL || qR) { // 至少一個存在才有意義
                qQ.push(qL, qR) // 依次推入比較數組，實際上就是廣度優先
            }
        }
    }

    return res
};

結果：

  • 57/57 cases passed (64 ms)
  • Your runtime beats 73.27 % of javascript submissions
  • Your memory usage beats 15.53 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n) ，n 為節點個數

查閱他人解法

思路基本上都是這兩種，未發現方向不同的解法。

思考總結

一般碰到二叉樹的題，要麼就深度遍歷，要麼就廣度遍歷。深度優先，也叫先序遍歷。

101.對稱二叉樹

題目地址

題目描述

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

示例：

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下麵這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

   1
   / \
  2   2
   \   \
   3    3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

題目分析設想

還是一道二叉樹的題，所以常規思路就是遍歷操作，深度優先或廣度優先都可。鏡像對稱可以觀察到很明顯的特點是有相同的根節點值，且每個樹的右子樹與另一個樹的左字數對稱相等。深度優先的方式，其實就是遞歸的思路，符合題目的說明。

編寫代碼驗證

Ⅰ.深度優先

代碼：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    function isMirror (l, r) {
        if (l === null && r === null) return true
        if (l === null || r === null) return false

        return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)
    }
    return isMirror(root, root)
};

結果：

  • 195/195 cases passed (68 ms)
  • Your runtime beats 87.74 % of javascript submissions
  • Your memory usage beats 41.48 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(n) ，n 為節點個數

Ⅱ.廣度優先

代碼：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 初始隊列
    let q = [root.left, root.right]
    // 依次將同級push進隊列，每次取兩個對稱節點進行判斷
    while(q.length) {
        let l = q.shift()
        let r = q.shift()
        if (l === null && r === null) continue
        if (l === null || r === null) return false
        if (l.val !== r.val) return false

        q.push(l.left, r.right, l.right, r.left)
    }
    return true
};

結果：

  • 195/195 cases passed (64 ms)
  • Your runtime beats 94.88 % of javascript submissions
  • Your memory usage beats 28.3 % of javascript submissions (35.6 MB)
  • 時間複雜度 O(n) ，n 為節點個數

查閱他人解法

看到一個有意思的思路，將樹按照左中右的順序輸入到數組，加上層數，該數組也是對稱的。

Ⅰ.左中右順序輸出數組

代碼：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 輸出數組
    let arr = []
    search(arr, root, 1);
    // 入參分別為輸出，節點和層級
    function search(output, n, k) {
        if (n.left !== null) {
            search(output, n.left, k+1)
        }

        if (n.right !== null) {
            search(output, n.right, k + 1);
        }
    }
     //判斷是否對稱
     let i = 0, j = arr.length - 1
     while (i < j) {
         if (arr[i] != arr[j]) {
             return false
         }
         i++
         j--
     }
     return true
};

結果：

  • 195/195 cases passed (72 ms)
  • Your runtime beats 76.3 % of javascript submissions
  • Your memory usage beats 6.11 % of javascript submissions (36.3 MB)
  • 時間複雜度 O(n) ，n 為節點個數

思考總結

這道題的大致解法都是遍歷節點或者利用隊列，只是在遞歸的細節上會有些差異。左中右輸出數組的思路很清奇，雖然效率明顯會更低下，但是不失為一種思路。

104.二叉樹的最大深度

題目地址

題目描述

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

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

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

題目分析設想

這道題最基本的思路就是計算出每條子節點的深度，再進行比較。為了提升效率，可以增加同級比對，去除不可能是最長節點的葉節點計算。

所以這裡我就用以下幾種思路來實現深度優先演算法。

  • 遞歸，直接獲取子樹最大高度加 1
  • 利用隊列，求深度轉化為求有多少層

編寫代碼驗證

Ⅰ.遞歸

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 左側子樹的最大高度
    let l = maxDepth(root.left)
    // 右側子樹的最大高度
    let r = maxDepth(root.right)
    return Math.max(l, r) + 1
};

結果：

  • 39/39 cases passed (60 ms)
  • Your runtime beats 99 % of javascript submissions
  • Your memory usage beats 45.77 % of javascript submissions (37.1 MB)
  • 時間複雜度 O(n) ，n 為節點個數

Ⅱ.利用隊列

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 隊列
    let q = [root]
    let dep = 0
    while(q.length) {
        let size = q.length
        dep++
        while(size > 0) {
            let node = q.shift()
            if (node.left !== null) q.push(node.left)
            if (node.right !== null) q.push(node.right)
            size--
        }
    }
    return dep
};

結果：

  • 39/39 cases passed (68 ms)
  • Your runtime beats 91.33 % of javascript submissions
  • Your memory usage beats 30.1 % of javascript submissions (37.2 MB)
  • 時間複雜度 O(n) ，n 為節點個數

查閱他人解法

這裡看到一個用棧的角度來實現的，取棧高度的最大值，其他的基本都是迴圈的細節差異，大體思路一致。

Ⅰ.利用棧

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 棧
    let s = [{
        node: root,
        dep: 1
    }]
    let dep = 0

    while(s.length) {
        // 先進後出
        var cur = s.pop()
        if (cur.node !== null) {
            let curDep = cur.dep
            dep = Math.max(dep, curDep)
            if (cur.node.left !== null) s.push({node: cur.node.left, dep: curDep + 1})
            if (cur.node.right !== null) s.push({node: cur.node.right, dep: curDep + 1})
        }
    }
    return dep
};

結果：

  • 39/39 cases passed (72 ms)
  • Your runtime beats 81.41 % of javascript submissions
  • Your memory usage beats 66.6 % of javascript submissions (37 MB)
  • 時間複雜度 O(n) ，n 為節點個數

思考總結

二叉樹的操作，一般就是深度優先和廣度優先，所以基本上就朝這兩個方向上去解，然後進行優化就可以了。

107.二叉樹的層次遍歷II

題目地址

題目描述

給定一個二叉樹，返回其節點值自底向上的層次遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）

例如：

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的層次遍歷為：

[
  [15,7],
  [9,20],
  [3]
]

題目分析設想

這道題在我看來還是兩種方式，深度優先和廣度優先。

  • 深度優先，記錄下每個節點對應的層數後，按層數反向輸出即可
  • 廣度優先，記錄下每層的節點後反向輸出

編寫代碼驗證

Ⅰ.深度優先

代碼：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    // 當前層級標識
    let idx = 0
    let res = []

    function levelOrder(node, floor, arr) {
        if (node === null) return arr
        if(arr[floor]) {
            arr[floor].push(node.val)
        } else {
            arr[floor] = [node.val]
        }
        levelOrder(node.left, floor + 1, arr)
        levelOrder(node.right, floor + 1, arr)
        return arr
    }

    return levelOrder(root, idx, res).reverse()
};

結果：

  • 34/34 cases passed (68 ms)
  • Your runtime beats 77.01 % of javascript submissions
  • Your memory usage beats 34.78 % of javascript submissions (34.7 MB)
  • 時間複雜度 O(n) ，n 為節點個數

Ⅱ.廣度優先

代碼：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if (root === null) return []
    // 初始隊列
    let q = [root]
    let res = []

    while(q.length) {
        // 當前層節點數量
        const count = q.length
        let curArr = []
        for(let i = 0; i < count;i++) {
            const node = q.shift()
            curArr.push(node.val)
            // 將子節點依次推入隊列
            if (node.left) q.push(node.left)
            if (node.right ) q.push(node.right )
        }
        res.push(curArr)
    }
    return res.reverse()
};

結果：

  • 34/34 cases passed (64 ms)
  • Your runtime beats 89.2 % of javascript submissions
  • Your memory usage beats 32.3 % of javascript submissions (34.7 MB)
  • 時間複雜度 O(n) ，n 為節點個數

查閱他人解法

沒有看到什麼特別的解法，主要都是按 BFS 和 DFS 來處理，要麼迭代，要麼遞歸等等。

這裡就介紹下別的吧，在第一種解法中我們使用的是前序優先，當然用中序優先或後序優先也可以，下麵代碼可以說明區別：

// 先序，順序為 根 -> 左 -> 右
function levelOrder(node, floor, arr) {
    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }

    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 中序，順序為 左 -> 根 -> 右
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)

   if(arr[floor]) {
       arr[floor].push(node.val)
   } else {
       arr[floor] = [node.val]
   }

    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 後序，順序為 左 -> 右 -> 根
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)

    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }
    return arr
}

思考總結

二叉樹的題目就根據情況在深度優先和廣度優先中擇優選擇即可，基本不會有太大的問題。

108.將有序數組轉換為二叉搜索樹

題目地址

題目描述

將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。

示例:

給定有序數組: [-10,-3,0,5,9],

一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下麵這個高度平衡二叉搜索樹：

      0
     / \
   -3   9
   /   /
 -10  5

題目分析設想

這裡有兩點要註意的：高度平衡二叉樹要求每個節點的左右兩個子樹的高度差的絕對值不超過 1；而二叉搜索樹要求左子樹上所有節點值小於根節點，右子樹上所有節點值大於根節點。

而題目給出的是一個有序的數組，所以可以直接考慮二分後進行處理，我這就直接遞歸作答：找到根節點，遞歸生成左右子樹。

編寫代碼驗證

Ⅰ.遞歸

代碼：

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null
    // 中位數，用偏移避免溢出
    const mid = nums.length >>> 1
    const root = new TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums.slice(0, mid))
    root.right = sortedArrayToBST(nums.slice(mid + 1))
    return root
};

結果：

  • 32/32 cases passed (80 ms)
  • Your runtime beats 70.72 % of javascript submissions
  • Your memory usage beats 29.79 % of javascript submissions (37.8 MB)
  • 時間複雜度 O(n)

查閱他人解法

這裡看到另外一種解法，先創建一個平衡二叉樹，然後中序遍歷樹同時遍曆數組即可，因為中序遍歷出來的剛好是有序數組。

Ⅰ.創建樹後中序遍曆數組賦值

代碼：

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null

    // 節點總數
    let len = nums.length
    let root = new TreeNode(-1);
    let q = [root]
    // 已經創建了根節點
    len--
    while(len) {
        const node = q.shift()
        // 左子樹
        const l = new TreeNode(-1)
        q.push(l)
        node.left = l
        len--
        if (len) {
            // 右子樹
            const r = new TreeNode(-1)
            q.push(r)
            node.right = r
            len--
        }
    }

    let i = 0
    inorder(root)
    function inorder(node) {
        if (node === null) return
        inorder(node.left)
        node.val = nums[i++]
        inorder(node.right)
    }

    return root
};

結果：

  • 32/32 cases passed (72 ms)
  • Your runtime beats 93.4 % of javascript submissions
  • Your memory usage beats 24.12 % of javascript submissions (37.8 MB)
  • 時間複雜度 O(n)

思考總結

這裡其實是個逆向思維，之前是二叉樹輸出數組，現在變成數組轉成二叉樹。剛好可以翻一下前序中序和後序的區別，這裡中序就可以了。不過這道題我還是更推薦遞歸二分求解。

（完）

本文為原創文章，可能會更新知識點及修正錯誤，因此轉載請保留原出處，方便溯源，避免陳舊錯誤知識的誤導，同時有更好的閱讀體驗
如果能給您帶去些許幫助，歡迎 ⭐️star 或 ✏️ fork
(轉載請註明出處：https://chenjiahao.xyz)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Layui下拉3級聯動
    這裡我就不給大家詳細說明瞭直接附圖： js代碼： layui.use(['layer', 'form','xform','layer'], function () { var element = layui.element; var form = layui.form; var layer = la ...
  • 函數的記憶----函數性能優化
    // 用n的階乘來演示 保存上一步計算的數據，進行下一次計算時候先判斷是否有上次執行過的，如果有直接獲取保存的值然後再進行下一步計算 // n! n*(n-1)*....*2*1 // 0! = 1 // n! = n*(n-1)! // 實現記憶前 var count = 0 // 執行的次數 f ...
  • JavaScript2 基礎
    運算符 賦值運算符 用於給變數賦值。 y=5;/z=2; 算術運算符 即算數符號，是基本算數運算。+ 加 / - 減/ * 乘/ / 除/ % 取餘數/ ++ 自增（y++先賦值再自增/++y先自增再賦值）/ -- 自減，和自增同理/ 複合運算符 += 加等 x+=y等同於 x=x+y 其它的原理相 ...
  • JavaScript1 基礎
    JavaScript的組成 ·ECMAScript 描述了語言的語法和基本對象/ ·DOM 文檔對象模型，描述處理網頁內容/ BOM 瀏覽器對象模型 描述與瀏覽器進行交互的方法和介面 引入方式/ head標簽內/body標簽內 一般在</body>結束標簽錢插入script的標簽 <script> ...
  • VueUI -- iView4.0簡單使用
    一、iView（View UI） 1、簡介 官網：https://www.iviewui.com/ 倉庫：https://github.com/view-design/ViewUI iView 與 View UI 本質上是一個東西，隨著版本的升級，iView （4.0）改名為 View UI。是一套 ...
  • 我的前端博客
    這個博客寫了好多前端的知識，有如下內容 "鏈接" ( ^▽^ )( ^▽^ )( ^▽^ ) "html" "css" "JavaScript" "jQuery" "ajax" "canvas" "nodejs" "mysql" "mongodb" "angular" 還有一些數據結構的知識和pyt ...
  • Mybatis的PageHelper分頁插件的PageInfo的屬性參數，成員變數的解釋,以及頁面模板
    作者:個人微信公眾號:程式猿的月光寶盒 項目中使用了Mybatis的PageHelper分頁插件後的js文件 js / 初始化首頁數據 / function initData(pageNo) { //清空原來的數據,找到第一個以外的tr,並移除,用 :gt() $("tr:gt(0)").remov ...
  • Ajax非同步按下回車提交表單
    1.Ajax非同步按下回車提交表單;2.isEmpty()判斷input框是否為空 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類