【Leetcode 做題學演算法周刊】第五期-有解無憂

首發于微信公眾號《前端成長記》，寫于 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,null,3,null,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 ，

題目分析設想

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

所以這里我就用以下幾種思路來實作深度優先演算法，

遞回，直接獲取子樹最大高度加 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],

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

[
  [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)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/165103.html

標籤：JavaScript

上一篇：axios統一介面管理及優化

下一篇：JS---DOM---元素相關的操作方法

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

背景

目錄

Easy

100.相同的樹

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

101.對稱二叉樹

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

104.二叉樹的最大深度

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

107.二叉樹的層次遍歷II

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

108.將有序陣列轉換為二叉搜索樹

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結